The Question that I have is as follows:
Given that $a_0 = 2$, $a_1 = 5,$ and $ a_{n+2} = 5a_{n+1} - 6{a_n}$, show that $a_n = 2^n + 3^n .$
How do I know how many base cases to prove? And once I have done so, how do I prove the inductive step?
It's is probably simple, but my textbook isn't proving to be very useful, and I cant seem to be able to apply any knowledge I get from videos to different problems.
Any help is appreciated, I have to sit my IB Maths Paper 3 next week!
On
Induction is about finding a way to express the statement for $k=n$ in terms of the statement for smaller $k$. If you're dealing with a recurrence relation, the "expression of bla bla in terms of smaller $k$" is quite explicit!
Assume, for all $k<n$, that $a_k = 2^k+3^k$. This way, $$a_n = 5a_{n-1} - 6a_{n-2} \stackrel{\text{I.H.}}{=}5(2^{n-1}+3^{n-1}) - 6(2^{n-2}+3^{n-2})$$ The rest has nothing to do with induction, just rearranging terms.
Let $P(n)$ be the proposition that $a_n = 2^n + 3^n$.
The statements $P(0)$ and $P(1)$ are the base cases, easy to show.
The 'strong' inductive step then is to show that for any $k \geq 0$
$$P(j) \ \text{ for all } 0 \leq j \leq k + 1 \ \Rightarrow \ P(k+2)$$
Have you tried writing it out? By hypothesis $P(k)$, that is $a_k = 2^k + 3^k$; and by $P(k+1)$ we have $a_{k+1} = 2^{k+1} + 3^{k+1}$. Thus
$$a_{k+2} = 5a_{k+1} - 6a_{k} = 5(2^{k+1} + 3^{k+1}) - 6(2^k + 3^k) = \ \cdots$$