How to continue? Induction.

• May 11th 2008, 01:05 PM
simplysparklers
How to continue? Induction.
Hi everyone!
I'm not sure what to do with this induction question, can anyone help me please?

Let a_1=0, a_2=3, and, for all n>=3 let
a_n= 1/2(a_(n-1) + a_(n-2))
By induction on n, show that for all n>=2,
a_n= 2 + 4(-1/2)^n.

What I did so far was work with the 2nd equation, and said:
let n=1
0= 2 + 4(-1/2)^1
= 2 - 2
=0
therefore it is true for n=1

Assume true for n=k
a_k= 2 + 4(-1/2)^k

...what's the next step for the proof?Or have I gone completely wrong from the beginning?? Thanks in advance for your help guys! (Bow)
• May 11th 2008, 01:42 PM
Plato
First step: $\displaystyle a_3 = \frac{{a_1 + a_2 }}{2} = \frac{3}{2} = 2 + 4\left( { - \frac{1}{2}} \right)^3.$

Now assume that $\displaystyle a_K = 2 + 4\left( { - \frac{1}{2}} \right)^K$ is true.
Look at the next step.
$\displaystyle a_{K + 1} = \frac{{a_K + a_{K - 1} }}{2} = \frac{{2 + 4\left( { - \frac{1}{2}} \right)^K + 2 + 4\left( { - \frac{1}{2}} \right)^{K - 1} }}{2}$
$\displaystyle \frac{{2 + 4\left( { - \frac{1}{2}} \right)^K + 2 + 4\left( { - \frac{1}{2}} \right)^{K - 1} }}{2} = 2 + 2\left( { - \frac{1}{2}} \right)^{K + 1} \left[ {\left( { - \frac{1}{2}} \right)^{ - 1} + \left( { - \frac{1}{2}} \right)^{ - 2} } \right]$
Can you finish?
• May 11th 2008, 01:45 PM
PaulRS
In this case you'll have to assume that it's true for $\displaystyle a_{n-1}$ and $\displaystyle a_{n}$ and then show it's true for $\displaystyle a_{n+1}$

(this is a stronger form of induction)
• May 11th 2008, 01:52 PM
Moo
Quote:

Originally Posted by PaulRS
In this case you'll have to assume that it's true for $\displaystyle a_{n-1}$ and $\displaystyle a_{n}$ and then show it's true for $\displaystyle a_{n+1}$

(this is a stronger form of induction)

"Strong induction" is the name :D

This means that the property is true for any k<n, and then show that it's true for n ^^
• May 11th 2008, 01:56 PM
TheEmptySet
Quote:

Originally Posted by simplysparklers
Hi everyone!
I'm not sure what to do with this induction question, can anyone help me please?

Let a_1=0, a_2=3, and, for all n>=3 let
a_n= 1/2(a_(n-1) + a_(n-2))
By induction on n, show that for all n>=2,
a_n= 2 + 4(-1/2)^n.

What I did so far was work with the 2nd equation, and said:
let n=1
0= 2 + 4(-1/2)^1
= 2 - 2
=0
therefore it is true for n=1

Assume true for n=k
a_k= 2 + 4(-1/2)^k

...what's the next step for the proof?Or have I gone completely wrong from the beginning?? Thanks in advance for your help guys! (Bow)

Our base case is n=3

$\displaystyle a_3=\frac{1}{2}(0+3)=\frac{3}{2}$
also
$\displaystyle a_3=2+4\left( -\frac{1}{2}\right)^3=2-\frac{1}{2}=\frac{3}{2}$

So the base case checks

We need to use "strong" (you may know it by another name)mathematical induction

assume true of all k < n use this to prove n is true

We want to show $\displaystyle \frac{1}{2}(a_{n-1}+a_{n-2})=a_n$

since n-1,n-2 < n they are true by the induction hypothesis

$\displaystyle \frac{1}{2}(a_{n-1}+a_{n-2})=\frac{1}{2}(2+4\left( -\frac{1}{2}\right)^{n-2}+2+4\left( -\frac{1}{2}\right)^{n-1})=$

$\displaystyle 2+2\left( -\frac{1}{2}\right)^{n-2}+2\left( -\frac{1}{2}\right)^{n-1}=2+2\left( -\frac{1}{2}\right)^{n-2}\left( 1+\left(-\frac{1}{2}\right) \right)=$

$\displaystyle 2+2\left( -\frac{1}{2}\right)^{n-2}\left( \frac{1}{2}\right)=2+\left( -\frac{1}{2}\right)^{n-2}=$

$\displaystyle 2+\underbrace{(4)\left( -\frac{1}{2}\right)^2}_{=1}\left( -\frac{1}{2}\right)^{n-2}=2+4\left( -\frac{1}{2}\right)^n=a_n$

QED
• May 12th 2008, 07:48 AM
simplysparklers
Thank you so much all you guys for your help! (Flower)

One more question , and then I think I'm done with this lot of questions (Tongueout), the end of this question after the induction is:
deduce that (a_n) $\displaystyle \rightarrow$ 2.

What I did so far was:
|a_n- $\displaystyle \alpha$ | = |2+4(-1/2)^n-2|
= |4(-1/2)^n|

....what do I do from here please? How do I prove 2 is $\displaystyle \alpha$ ??
• May 12th 2008, 08:13 AM
Plato
Quote:

Originally Posted by simplysparklers
One more question ,
deduce that (a_n) $\displaystyle \rightarrow$ 2.

Well, $\displaystyle \left( {\frac{{ - 1}}{2}} \right)^n \to 0$.
• May 12th 2008, 08:25 AM
simplysparklers
But what if n is negative, then it doesn't approach 0??
• May 12th 2008, 08:42 AM
Plato
Quote:

Originally Posted by simplysparklers
But what if n is negative, then it doesn't approach 0??

How can n be negative?
It is an index of a sequence.
To find the limit of the sequence, n approaches infinity and is therefore positive.
• May 12th 2008, 08:54 AM
simplysparklers
Oh of course!Duh me! (Headbang) Thanks Plato!!& sorry for all the silly questions, I'm just not getting the whole concept of sequences at all!!(Shake)