General Structuring of Recursive Induction

Question

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

1. Prove true for $n=1$
2. Assume true for $n=k$
3. 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!

Answer 1

Doing recursive induction is not really any different in general from induction in other situations. However, for your particular question, you should use strong induction to prove your stated result since it involves using $2$ previous values. First, I assume the recursive statement is

$$u_n=11u_{n-1}-28u_{n-2}, \; n \ge 3 \tag{1}\label{eq1A}$$

where your stated second term being $-28u_{n-1}$ is a typo. The statement you're asking to prove is

$$u_n=7^n-4^n, \; n \ge 1 \tag{2}\label{eq2A}$$

You first check your $2$ base cases. You have $u_1 = 3$, with \eqref{eq2A} giving $u_1 = 7 - 3$, so it matches. Similarly, \eqref{eq2A} gives $u_2 = 7^2 - 4^2 = 49 - 16 = 33$, which matches the given base case of $u_2 = 33$.

Next, assume that for some integer $k \ge 2$, \eqref{eq2A} holds for all positive integers $n \le k$ (this is the strong induction part). Using this assumption, then for $n = k + 1$, \eqref{eq1A} gives

$$\begin{equation}\begin{aligned} u_{k+1} & = 11u_k - 28u_{k-1} \\ & = 11(7^k - 4^k) - 28(7^{k-1} - 4^{k-1}) \\ & = 11(7^k) - 11(4^k) - \left((4)(7)\right)(7^{k-1}) + \left((7)(4)\right)(4^{k-1}) \\ & = 11(7^k) - 11(4^k) - 4(7^{k}) + 7(4^{k}) \\ & = 7(7^k) - 4(4^k) \\ & = 7^{k+1} - 4^{k+1} \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

This matches what is expected from \eqref{eq2A}, showing that it also holds for $n = k + 1$. Thus, by strong induction, \eqref{eq2A} is true for all $n \ge 1$.

FYI, you could also more directly find and prove \eqref{eq2A} by determining & using the characteristics roots of \eqref{eq1A} such as explained in Linear difference equation.