Using complete induction, prove that if $a_1=2$, $a_2=4$, and $a_{n+2}=5a_{n+1}-6a_n$, then $a_n=2^n$

Question

Could anyone please explain to me how to do this problem by using the principle of complete induction? Thanks. :)

Let $a_1=2$, $a_2=4$, and $a_{n+2}=5a_{n+1}-6a_n$ for all $n\geq 1$. Prove that $a_n=2^n$ for all natural numbers $n$.

Answer 1

For induction we wish to show the following:

1. If $a_{n+2} = 2^{n+2}$ and $a_{n+1} = 2^{n+1}$ for some particular positive integer $n$ then: $a_{n+3} = 2^{n+3}$ must be true for that same value $n$

2. $a_1 = 2^1$ and $a_2 = 2^2$

Since if 1 is true and 2 is true then we can repeatedly use 1 from the truth of 2 to establish that

1. $a_n = 2^n$ for all $n >= 1$

Proving point number 2 is trivial. It is already given to us. We now must prove point number 1.

1. Assume that

$$a_{n+2} = 2^{n+2}$$

$$a_{n+1} = 2^{n+1}$$

For some arbitrary positive integer n.

1. Notice that using the original definition:

$$a_{n+3} = 5*a_{n+2} - 6*a_{n+1} = 5*2^{n+2} - 6*2^{n+1}$$

Now we will simplify this expression:

$$5*2^{n+2} - 6*2^{n+1} =2*(5*2^{n+1})- (5*2^{n+1}) - 2^{n+1}$$

We now factor and reorganize:

$$2*(5*2^{n+1})- (5*2^{n+1}) - 2^{n+1} =(5*2^{n+1})(2 - 1) - 2^{n+1} = (5*2^{n+1}) - 2^{n+1} $$

And now simplify:

$$ (5*2^{n+1}) - 2^{n+1} = 4*2^{n+1} = 2*2^{n+2} = 2^{n+3} $$

Thus we have shown: that if

$$a_{n+2} = 2^{n+2}$$

$$a_{n+1} = 2^{n+1}$$

and

$$a_{n+3} = 5*a_{n+2} - 6*a_{n+1}$$

Then:

$$a_{n+3} = 2^{n+3}$$

Thus we are now done with the induction.

Answer 2

It’s pretty straightforward; you really need only follow the models that you’ve already seen. Your induction hypothesis will be that $a_k=2^k$ for $k=1,2,\dots,n$, where $n$ is any integer greater than $2$, and your induction step will then be

$$\begin{align*} a_{n+1}&=5a_n-6a_{n-1}&&\text{by the given recurrence}\\ &=5\cdot2^n-6\cdot2^{n-1}&&\text{by the induction hypothesis}\\ &=5\cdot2\cdot2^{n-1}-6\cdot2^{n-1}&&\text{to get a common factor}\\ &=(10-6)2^{n-1}&&\text{pulling out the common factor}\\ &=\ldots \end{align*}$$

Can you finish the calculation?

Answer 3

We give a slightly odd solution that you are probably not intended to use, but it may be informative. Let $b_n=2^n$. It is clear that the sequence $(b_n)$ satisfies the initial conditions $a_1=2$ and $b_2=4$. We can also verify that $b_{n+2}=5b_{n+1}-6b_{n}$ for all $n \ge 3$. For $$5b_{n+1}-6b_n=5\cdot 2^{n+1}-6\cdot 2^n=2^n[10-6]=2^{n+2}=b_{n+2}.$$

Now all we need is the following result.

Lemma: Suppose that two arbitrary sequences $(a_n)$ and $(b_n)$ satisfy the second-order (not necessarily linear) recurrence $x_{n+2}=f(n,x_{n+1}, x_n)$ and satisfy the conditions $a_1=b_1$ and $a_2=b_2$. Then $a_n=b_n$ for all $n\ge 1$.

Proof: This is automatically true for $n=1$ and $n=2$. Suppose that for all $k\le n+1$, we have $a_k=b_k$. We will show that $a_{k+2}=b_{k+2}$. This is obvious. For $$a_{k+2}=f(k,a_{k+1}, a_k)=f(k,b_{k+1},b_k)=b_{k+2}.$$

Remark: We produced an induction proof of the lemma, since an induction proof was asked for. The lemma has not much to do with our particular sequences, and can be proved for more general recurrences that $x_{n+2}=f(n,x_{n+1}, x_n)$. Once the lemma has been proved, it can be applied to any (say second order) recurrence, if we have a reasonable conjecture as to the solution. All we need to do is plug in the proposed solution and check whether the recurrence holds.