3
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ Just as a note, you can auto align things using the align mode. Separate lines with \\ and set tabs with &. $\endgroup$ Jul 17 '17 at 22:54
  • $\begingroup$ You seem to be missing a term in the definition of the recurrence relation. $\endgroup$
    – Bram28
    Jul 17 '17 at 22:59
  • $\begingroup$ Sorry I missed a term. I have updated the question $\endgroup$
    – user444945
    Jul 17 '17 at 23:00
  • 1
    $\begingroup$ @JoshMitkitzel Exactly. THough some would consider this weak induction, but with an expanded (though fixed size) base. $\endgroup$
    – Bram28
    Jul 17 '17 at 23:04
  • 1
    $\begingroup$ @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. $\endgroup$
    – Bram28
    Jul 17 '17 at 23:07
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy