# Induction Sequence

• Nov 5th 2009, 08:33 AM
kentwoods
Induction Sequence
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
• Nov 5th 2009, 08:38 AM
Defunkt
Quote:

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?
• Nov 5th 2009, 08:42 AM
kentwoods
yea looks like 2n + 1 ?

How would I show this by induction tho?
• Nov 5th 2009, 08:59 AM
Defunkt
Quote:

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$
.
.
.
• Nov 5th 2009, 09:15 AM
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
• Nov 5th 2009, 09:43 AM
Defunkt
Quote:

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.
• Nov 5th 2009, 09:56 AM
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.
• Nov 5th 2009, 10:11 AM
Defunkt
Quote:

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).
• Nov 5th 2009, 10:14 AM
kentwoods
no I meant the latter, i meant assume for n-1 and prove for n