Given $a_{n} = 3a_{n-1}-2a_{n-2}$, $a_0=0$, $a_1 = 2$. Show $a_n = 2(2^n-1)$ by induction

This is my problem:

The recurrence relation is \begin{aligned} a_{n} = 3a_{n-1}-2a_{n-2} \end{aligned} This is given that $$a_{0}=0, a_{1}=2$$.

From the above information I calculated

\begin{aligned} a_{2} &=3(a_{2 - 1}) - 2(a_{2 - 2}) = 3(a_{1}) - 2(a_{0}) = 3(2) - 2(0) = 6 \\ a_{3} &=3(a_{3 - 1}) - 2(a_{3 - 2}) = 3(a_{2}) - 2(a_{1}) = 3(6) - 2(2) = 14 \\ a_{4} &=3(a_{4 - 1}) - 2(a_{4 - 2}) = 3(a_{3}) - 2(a_{2}) = 3(14) - 2(6) = 30 \end{aligned}

I have been trying to solve this recurrence relation for quite some time and have come up with the solution

\begin{aligned} a_{n} = 2 * (2^{n} - 1) \end{aligned}

I am having trouble proving this solution by induction.

My Attempt:

Base Cases:

$$a_0 = 0 = 2(2^0-1)\\a_1 = 2 = 2(2^1-1)$$

Inductive Hypothesis: Assume that $$a_k = 2(2^k-1)$$ and $$a_{k-1} = 2(2^{k-1}-1)$$

Inductive Step: $$a_{k+1} = 3a_{(k+1)-1}-2a_{(k+1)-2} = 3a_{k}-2a_{k-1}$$

By the inductive hypothesis $$a_k = 2(2^k-1)$$ and $$a_{k-1} = 2(2^{k-1}-1)$$,

$$a_{k+1}= 3 ( 2 (2^k-1) - 2 (2(2^{k-1}-1)).$$

From here it is just simplifying but I cannot get it to simplify to the correct expression.

Any ideas?

• Write $3=2+1$ and remember that $2^{n-1}-2^{n-2} = 2^{n-2}$.
– user208649
Commented Sep 22, 2020 at 10:39
• You're missing a ) Commented Sep 22, 2020 at 10:41

Assume it holds for $$n=k$$ (so it also holds for $$n), then for the induction step \begin{align} a_{k+1}&=3a_{k}-2a_{k-1}\\ &=3(2(2^{k}-1))-2(2(2^{k-1}-1))\\ &=3(2^{k+1}-2)-2(2^{k}-2)\\ &=3\cdot2^{k+1}-6-2^{k+1}+4\\ &=2\cdot2^{k+1}-2\\ &=2(2^{k+1}-1) \end{align}

as required.

• I claim that this is by no means an inductive proof. Can you state clearly the induction hypothesis (i.e. some $P(k)$), and where $P(k)\implies P(k+1)$ ?
– user65203
Commented Sep 24, 2020 at 12:39
• $P(k),P(k-1)\implies P(k+1)$ from the second equality. Commented Sep 24, 2020 at 12:42
• What is $P(k)$ ?
– user65203
Commented Sep 24, 2020 at 12:42
• $P_{k}=a_{k}$. The OP did induction above. Commented Sep 24, 2020 at 12:43
• $a_k$ is not a predicate, it is an element of a sequence. You cannot "prove" $a_k$, and even less write $a_k\implies a_{k+1}$.
– user65203
Commented Sep 24, 2020 at 12:44