Proof by Induction - in Sequences.

[johnny009]

Dear ALL,

My last Question of the Day?

Let b1 and b2 be a sequence of numbers defined by:

\(\displaystyle b_{n}=b_{n-1}+2b_{n-2}\) where $b_1=1,\,b_2=5$ and $n\ge3$

a) Write out the 1st 10 terms.

b) Using strong Induction, show that:

\(\displaystyle b_n=2^n+(-1)^n\)

Many Thanks

John C.

 

[HallsofIvy]

Interesting question. I am puzzled as to why you have shown no attempt at all to do anything on this yourself. Don't you think it is interesting?

You are given the recursive definition: $b_n= b_{n-1}+ 2b_{n-2}$ with $b_1= 1$ and $b_2= 5$.

1. Write out the first ten terms.
$b_1= 1$
$b_2= 5$
$b_3= b_2+ 2b_1= 5+ 2(1)= 7$
$b_4= b_3+ 2b_2= 7+ 2(5)= 17$
$b_5= b_4+ 2b_3= 17+ 2(7)= 31$
$b_6= b_5+ 2b_4= 31+ 2(17)= 65$
$b_7= b_6+ 2b_5= 65+ 2(31)= 127$
$b_8= b_7+ 2b_6= 127+ 2(65)= 257$
$b_9= b_8+ 2b_7= 257+ 2(127)= 511$
$b_{10}= b_9+ 2b_8= 511+ 2(257)= 1025$

2. Using strong induction show that $b_n= 2^n+ (-1)^n$ for all $n\ge 1$.
I thought I recognized some of those numbers! 1= 2- 1, 5= 4+ 1, 7= 8- 1, 17= 16+ 1, 31= 32- 1, etc.

Strong induction requires proving that statement P(n)
1) is true for n= 1
2) if P(k) is true for all $k\le n$ then P(n+1) is true.

That is sufficient to conclude "P(n) is true for all $n\ge 1$".

Here, P(n) is "$b_n= 2^n+ (-1)^n$". P(1) is $b_1= 2^1- 1= 1$ which is true.

Now, suppose the statement is true for all $k\le n$. Then it is, specifically, true for n and n- 1.
We know that $b_{n+1}= b_{n}+ 2b_{n-1}= 2^n+ (-1)^n+ 2(2^{n-1}+ (-1)^{n-1})$.

So $b_{n+1}= 2^n+ (-1)^n+ 2^n+ (-1)^{n-1}= 2(2^n)+ (-1)^n+ 2(-1)^{n-1}$.

Look at two cases:
1) n is odd. Then n-1 is even so $(-1)^n= -1$ and $(-1)^{n-1}= 1$. $(-1)^n+ 2(-1)^{n-1}= -1+ 2= 1$.
2) n is even. Then n- 1 is odd so $(-1)^n= 1$ and $(-1)^{n-1}= -1$. $(-1)^n+ 2(-1)^{n-1}= 1- 2= -1$.
So if n is odd, $b_{n+1}= 2(2^n)+ 1= 2^{n+1}+ (-1)^{n+ 1}$ and if n is even $b_{n+1}= 2(2^n)- 1= 2^{n+1}+ (-1)^{n+1}$.

In either case, $b_{n+1}= 2^{n+1}+ (-1)^{n+1}$ and we are done.

 

[MarkFL]

Dear ALL,

My last Question of the Day?

Let b1 and b2 be a sequence of numbers defined by:

\(\displaystyle b_{n}=b_{n-1}+2b_{n-2}\) where $b_1=1,\,b_2=5$ and $n\ge3$

a) Write out the 1st 10 terms.

b) Using strong Induction, show that:

\(\displaystyle b_n=2^n+(-1)^n\)

Many Thanks

John C.

Another way to find the closed form (I know induction is required for the assignment, but I post this just to show another method) would be to write the given recursion as:

\(\displaystyle b_{n}-b_{n-1}-2b_{n-2}=0\)

We have a linear homogeneous recursion, whose associated characteristic equation is:

\(\displaystyle r^2-r-2=(r-2)(r+1)=0\)

As the roots are:

\(\displaystyle r\in\{-1,2\}\)

We know the closed form will be:

\(\displaystyle b_{n}=c_12^n+c_2(-1)^n\)

Where the parameters $c_i$ can be determined from the given initial conditions:

\(\displaystyle b_{1}=c_12^1+c_2(-1)^1=2c_1-c_2=1\)

\(\displaystyle b_{2}=c_12^2+c_2(-1)^2=4c_1+c_2=5\)

Solving the 2X2 system, we determine:

\(\displaystyle \left(c_1,c_2\right)=(1,1)\)

Hence, the solution satisfying all given conditions is:

\(\displaystyle b_{n}=2^n+(-1)^n\)