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

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

4. Good one!