1. Difficult Mathematical Induction

a0 = 2, a1 = 3

for any k ≥ 2 (k is a whole number)

ak = 3ak-1 - 2ak-2

Prove: an = 2^(n) + 1

2. Originally Posted by MATNTRNG
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: $a_0=2=2^0+1$, $a_1=2=2^1+1$

Yielding case: Assume $a_k = 2^k+1$ and $a_{k-1} = 2^{k-1}+1$.

$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.

3. Originally Posted by MATNTRNG
a0 = 2, a1 = 3

for any k ≥ 2 (k is a whole number)

ak = 3ak-1 - 2ak-2

Prove: an = 2^(n) + 1
It is true for $k=0,1$ . Assume truth for all indexes up to $k-1$ and show now for $k$ :

$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$ $
=2\cdot 2^{k-1}+1=2^k+1\,\,\,\,\square$

Tonio

4. Good one!