Induction Sequence

**kentwoods** · November 5th 2009, 08:33 AM

an = 1 + 2an-1
a1 = 1
a)Guess what an is based on inspection of this sequence
b) Prove the expression in (a) using induction

edit: ah my subscript got messed up, dunno how to post it on forums

suppose to be a subscript n = 1 + 2a subscript n-1
a subscript 1 = 1

**Defunkt** · November 5th 2009, 08:38 AM

Originally Posted by kentwoods

an = 1 + 2an-1
a1 = 1
a)Guess what an is based on inspection of this sequence
b) Prove the expression in (a) using induction

edit: ah my subscript got messed up, dunno how to post it on forums

suppose to be a subscript n = 1 + 2a subscript n-1
a subscript 1 = 1

$a_n = \{1,3,7,15,31,63,...\}$

Can you see the general pattern in the difference of every two successive elements?

**kentwoods** · November 5th 2009, 08:42 AM

yea looks like 2n + 1 ?

How would I show this by induction tho?

**Defunkt** · November 5th 2009, 08:59 AM

Originally Posted by kentwoods

yea looks like 2n + 1 ?

How would I show this by induction tho?

How is it 2n+1?

You have odd numbers there, yes, but the nth number is definitely not 2n+1...

Look at it this way:

$3-1 = 2$
$7-3 = 4$
$15-7 = 8$
$31-15 = 16$

What do 2,4,8,16 have in common?

Or, look at it this way:

$1= 2-1$
$3 = 4-1$
$7 = 8-1$
$15 = 16-1$
.
.
.

**kentwoods** · November 5th 2009, 09:15 AM

hmm

$2^n -1$

i think thats what you were trying to show me, im really bad when it comes to this

I cannot visualize it easily

**Defunkt** · November 5th 2009, 09:43 AM

Originally Posted by kentwoods

hmm

$2^n -1$

i think thats what you were trying to show me, im really bad when it comes to this

I cannot visualize it easily

Yes, that is correct. Now, we need to prove that $a_n = 2^n -1$ by induction.

Basis: n=1: $a_1 = 1, 2^1-1 = 1 = a_1 \Rightarrow$ correct.

Assume that it holds for n (that is, $a_n = 2^n-1$ ), and now we need to prove that it is correct for $n+1$ , that is, we need to prove that $a_{n+1} = 2^{n+1}-1$ .

$a_{n+1} = 1+2a_{n} \overbrace{=}^{\text{By the assumption for n}} 1+ 2\cdot (2^n-1) = 1 + 2 \cdot 2^n - 2 = 2 \cdot 2^n - 1 =$ $2^{n+1}-1 \Rightarrow a_{n+1} = 2^{n+1}-1$ which is what we wanted to prove, therefore the assumption holds for any $n \in \mathbb{N}$ and we are done.

**kentwoods** · November 5th 2009, 09:56 AM

Thanks mate, that actually makes a lot of sense when i go through it slowly

Just a quick question though, when we went over examples in class we always proved n-1 instead of n+1. Basically if one is true the one before it is true as well. I'm assuming this works the same way.

**Defunkt** · November 5th 2009, 10:11 AM

Originally Posted by kentwoods

Thanks mate, that actually makes a lot of sense when i go through it slowly

Just a quick question though, when we went over examples in class we always proved n-1 instead of n+1. Basically if one is true the one before it is true as well. I'm assuming this works the same way.

I don't think I follow. Did you assume that it is correct for n and prove for n-1? Or assume correct for n-1 and prove for n? If the latter, then that is equivalent to what I did. Otherwise, that is not the way to use induction (it is not correct).

**kentwoods** · November 5th 2009, 10:14 AM

no I meant the latter, i meant assume for n-1 and prove for n

thanks for your help again

Thread: Induction Sequence

LinkBack

Thread Tools

Display

Induction Sequence

Similar Math Help Forum Discussions

[SOLVED] Induction on a sequence

Fibonacci Sequence - Induction Proof

induction on a reccurence sequence

Induction, sequence, not hard, please help me

Induction on a sequence

Search Tags