a0 = 2, a1 = 3
for any k ≥ 2 (k is a whole number)
ak = 3ak-1 - 2ak-2
Prove: an = 2^(n) + 1
Let's use a stronger form of induction here.
Base case: $\displaystyle a_0=2=2^0+1 $, $\displaystyle a_1=2=2^1+1 $
Yielding case: Assume $\displaystyle a_k = 2^k+1 $ and $\displaystyle a_{k-1} = 2^{k-1}+1 $.
$\displaystyle a_{k+1} = 3a_k-2a_{k-1} = 3(2^k+1)-2(2^{k-1}+1) = 3\cdot2^k+3-2^k-2 = 2\cdot2^k+1 = 2^{k+1}+1 $
By our use of induction, we're done.
It is true for $\displaystyle k=0,1$ . Assume truth for all indexes up to $\displaystyle k-1$ and show now for $\displaystyle k$ :
$\displaystyle a_k=3a_{k-1}-2a_{k-2}=3(2^{k-1}+1)-2(2^{k-2}+1)=3\cdot 2^{k-1}+3-2\cdot 2^{k-2}-2$ $\displaystyle
=2\cdot 2^{k-1}+1=2^k+1\,\,\,\,\square$
Tonio