proof verification - Proving formula of a recursive sequence using strong induction

Question:

A sequence is defined recursively by $ a_1 = 1, a_2 = 4, a_3 = 9$ and $ a_n = a_{n-1} - a_{n-2} + a_{n-3} + 2(2n-3)$ for $ n \ge 4$. Prove that $ a_n = n^{2}$ for all $ n \ge 1$.

My attempt:

Proof by strong induction:

Base Case: $ n =1, a_1 = (1)^{2} = 1 \ ,$
$ n = 2, a_2 = (2)^{2} = 4 \,$
$ n = 3, a_3= (3)^{2} = 9. \ $
So Base Case holds.

I.H: Assume the result is true for $ n = 1, 2, ....., k \ge 3$

Want to prove $\ a_{k+1} = (k+1)^{2}$.

$\begin{align}
a_{k+1} &= a_k - a_{k-1} + a_{k-2} + 2(2(k+1) -3)\text{, by recurrence relation}
\\& = k^{2} - (k-1)^{2} + (k-2)^{2} + 4k-2\text{, by I.H}
\\& = k^{2} - k^{2} + 2k -1 + k^{2} -4k + 4+4k -2
\\& = k^{2} + 2k + 1

\\& = (k+1)^{2}
\end{align}$

Hence, by strong induction, the result holds for all natural numbers.

Is this the correct way to prove a formula for a recursive sequence using strong induction?

Answer

You did well, and the proof is all good!

As far as your follow-up questions go:

The recurrence relation should tell you how many bases cases you need. In particular, look at the term that goes 'furthest back'. E.g. If you have a recurrence relation

$$a_n= 2a_{n-4}+6a_{n-2}$$

Then you will need $4$ base cases, since you go $4$ back.