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?
Best 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.