I'm currently learning recursive induction, but I'm really struggling on how to do recursive induction questions.
I'm fine with normal induction (i.e. prove that $1+2+3+...+n=\frac{n(n+1)}2$, and prove that $6^n+4$ is divisible by 5 for all positive integer $n$) and I know how to set it out
- Prove true for $n=1$
- Assume true for $n=k$
- Prove true for $n=k+1$
My understanding for working out recursive induction is that you have to assume that $n=k$, as well as $n=k+1$, are true or something.
Is there a set out way of doing recursive induction, and/or is there a textbook that has a really good explanation on how to do recursive induction?
Here's a question that I have to do
A sequence is defined recursively as $u_1=3$, $u_2=33$ and $u_n=11u_{n-1}-28u_{n-2}$ for $n≥3$. Prove that $u_n=7^n-4^n$ for all positive integers $n$.
Appreciate the help!