Induction problem involving two base cases and two assumptions of truth in recurrence relation I am unsure why I have to use two base cases of n=1 and n=2 and also assume truth for n=k and n=k+2 to prove by induction that n=k+2 is true.
I was trying to solve this question below:

A sequence is given by the recurrence relation $u_{1}=5$,$\;u_{2}=13$, $\;u_{n+2}=5u_{n+1}-6u_{n}$,$\;n\ge1$. Prove that the general formula for the sequence is $u_{n}=2^n+3^n$.

My first attempt was just usual as normal induction problems, let n=1 for the base case and then assume truth for n=k and find that it is also true for n=k+1. However, the mark scheme says that:

Let n=1,
$\vdots$
$\therefore$ true for n=1.
Let n=2,
$\vdots$
$\therefore$ true for n=2.
Assume truth for n=k and n=k+1,
$u_{k}=2^k+3^k$
$u_{k+1}=2^{k+1}+3^{k+1}$
Let n=k+2,
$\vdots$
$\therefore$ true for n=k+2.
$\therefore$ The proposition is true for n=1 and n=2, and if true for n=k and n=k+1, it is also true for n=k+2. By the principle of mathematical induction, the proposition is true for $\forall n \in \mathbb{Z}^+, n\ge1.$

My question is the following:

*

*Why do we need to show the case that it is true for n=k+2 and not for n=k+1?

*Can we assume truth for both n=k and n=k+1 at the same time? In a usual induction problem, we assume truth for n=k and then see if this is also true for n=k+1. Then, in this case, wouldn't that already satisfy the condition since n=k and n=k+1 are true (assumed to be true)?

*Why do we need two base cases of n=1 and n=2?

 A: To answer "why do we need to do this?", let's consider what can go wrong if we don't.
We're given the following three facts:

*

*$u_1 = 5$

*$u_2 = 13$

*$u_{n+2} = 5 u_{n+1} - 6 u_n$
If we were able to complete the induction proof with a single base case, e.g. if we only had to prove that $u_1 = 2^1 + 3^1$, then if we changed the value of $u_2$ to, say, $14$, then none of the details of the proof would change, which means that we would still be able to prove that $u_n = 2^n + 3^n$ even though we now have a completely different sequence that must have its own closed form.
As for why we need to make two assumptions in the inductive hypothesis, notice that if you only assume that $u_k = 2^k + 3^k$ then you get as far as saying $u_{k+1} = 5 u_k - 6 u_{k-1} = 2^k + 3^k - 6 u_{k-1}$, but since you have no information (and have made no assumptions) about the behaviour of $u_{k-1}$ you can't progress any further.
A small aside: There is such a thing as strong induction, in which instead of assuming that $P(n)$ is true for some value $n = k$ you instead assume that $P(n)$ is true for every value $n = 1, 2, \ldots, k$ and use that to prove that $P(k + 1)$ is true, and hence $P(n)$ is true for every $n$. You can, in fact, prove that strong induction and regular induction are actually equivalent, i.e. you can turn any proof by strong induction into a proof by regular induction and vice versa, but usually applying strong induction is overkill.
We could, in fact, turn this proof into a more standard induction proof with a little trickery. Instead of having our statement $P(n)$ be "$u_n = 2^n + 3^n$", we could make it be "$u_n = 2^n + 3^n$ and $u_{n+1} = 2^{n+1} + 3^{n+1}$. If we do that, then the base case for $n = 1$ is exactly equal to the two initial values of $u_1 = 5$ and $u_2 = 13$, the induction hypothesis has the assumptions about $u_k$ and $u_{k+1}$ baked into it, and we wind up proving the formulas for $u_{k+1}$ and $u_{k+2}$, noting that the former is pretty trivial since we assumed the truth of that formula in the induction hypothesis.
