1. ## 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

2. 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
$\displaystyle a_n = \{1,3,7,15,31,63,...\}$

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

3. yea looks like 2n + 1 ?

How would I show this by induction tho?

4. 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:

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

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

Or, look at it this way:

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

5. hmm

$\displaystyle 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

6. Originally Posted by kentwoods
hmm

$\displaystyle 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 $\displaystyle a_n = 2^n -1$ by induction.

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

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

$\displaystyle 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 =$ $\displaystyle 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 $\displaystyle n \in \mathbb{N}$ and we are done.

7. 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.

8. 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).

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