Proof by Induction - Sequence of integers

Question

Suppose a sequence of integers $a_1$, $a_2$, ... is defined as:

$$a_1 = 3$$ $$a_2 = 6$$ $$a_n = 5a_{n-1} - 6a_{n-2} + 2$$ for all $n\ge3$

$\mathbf {Prove}$ $\mathbf {S(n)}$: $a_n = 1 + 2^{n-1} + 3^{n-1}$ for all $n\in\mathbb N$

What I have done:

$\mathbf {Base}$ $\mathbf {Case}$: n = 3

$$5a_{n-1} - 6a_{n-2} + 2 = 1 + 2^{n-1} + 3^{n-1}$$ $$5a_{3-1} - 6a_{3-2} + 2 = 1 + 2^{3-1} + 3^{3-1}$$ $$5a_{2} - 6a_{1} + 2 = 1 + 2^{2} + 3^{2}$$ $$5(6) - 6(3) + 2 = 1 + 2^{2} + 3^{2}$$ $$14 = 14$$

$\mathbf {Induction}$ $\mathbf {Hypothesis}$: n = k

$$S(k) = a_k = 1 + 2^{k-1} + 3^{k-1}$$ $$5a_{k-1} - 6a_{k-2} + 2 = 1 + 2^{k-1} + 3^{k-1}$$

$\mathbf {Inductive}$ $\mathbf {Step}$: n = k + 1

$$S(k+1) = a_{k+1} = 1 + 2^{k} + 3^{k}$$ $$5a_{k} - 6a_{k-1} + 2 = 1 + 2^{k} + 3^{k}$$

From here I'm not too sure how to proceed forward. Any hints will be helpful.

Answer 1

HINT: You could assume $S(k)$ and $S(k-1)$ to be true and prove $S(k+1)$. Also, prove $S(3)$ and $S(4)$ as base cases (could be thought of as a corollary of induction).

Answer 2

Your inductive step is to prove $S(k+1)=1+2^{k}+3^{k}$. Your first step is correct: replace $S(k+1)$ with its definition. Now you need to substitute in your induction hypothesis. For this you need both $a_k$ and $a_{k-1}$, which is where L__'s suggestion is valuable. Assuming you have proved it for both $S_k$ and $S_{k-1}$ you have $a_{k+1}=5a_k+6a_{k-1}+2=5(1+2^{k-1}+3^{k-1})-6(???)+???$

Added: $5(1 + 2^{k-1} + 3^{k -1}) - 6(1 + 2^{k-2} + 3^{k -2}) + 2\\ =5+5\cdot 2^{k-1}+5\cdot 3^{k-1}-6-6\cdot 2^{k-2}-6\cdot 3^{k-2}+2\\ =1+5\cdot2^{k-1}-6\cdot 2^{k-2}+5\cdot 3^{k-1}-6\cdot3^{k-2}\\ =1+(10-6)2^{k-2}+(15-5)3^{k-2}\\ =1+2^k+3^k$