# 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?

• Just as a note, you can auto align things using the align mode. Separate lines with \\  and set tabs with &. Jul 17 '17 at 22:54
• You seem to be missing a term in the definition of the recurrence relation. Jul 17 '17 at 22:59
• Sorry I missed a term. I have updated the question
– user444945
Jul 17 '17 at 23:00
• @JoshMitkitzel Exactly. THough some would consider this weak induction, but with an expanded (though fixed size) base. Jul 17 '17 at 23:04
• @JoshMitkitzel Well, the recurrence relation will tell you how many base cases you should have. But that will most likely coincide with the number of first terms given, sure. Jul 17 '17 at 23:07

$$a_n= 2a_{n-4}+6a_{n-2}$$
Then you will need $4$ base cases, since you go $4$ back.