5
$\begingroup$

Given sequence $a_1, a_2, ...$ where $a_1=1, a_2 = 4, a_3 = 9$ and when $n > 3, a_n = a_{n-1}-a_{n-2}+a_{n-3} + 2(2n-3)$. Prove that the equality $a_n = n^2$ is valid for every $n$if $n \in \mathbb N$

I am pretty sure I have to use strong induction here, but I'm not sure how to solve it. Any ideas?

$\endgroup$
4
$\begingroup$

Guide:

  • Verify that $a_n=n^2$ holds for $n \in \{ 1,2,3\}$.

  • Simplify $a_{n-1}-a_{n-2}\color{red}{+}a_{n-3}+2(2n-3)=(n-1)^2-(n-2)^2\color{red}{+}(n-3)^2+2(2n-3)$ and show that it is equal to $n^2$.

Credit:

Special thanks to Rene Schipperus for pointing out the mistake in the question and Donald Splutterwit for fixing the mistake.

$\endgroup$
  • 2
    $\begingroup$ There must be something wrong with the question since that expression is not $n^2$. $\endgroup$ – Rene Schipperus Nov 24 '17 at 0:36
  • $\begingroup$ Hmm.... you are right. The coefficient of $n^2$ is $-n^2$ $\endgroup$ – Siong Thye Goh Nov 24 '17 at 0:38
  • $\begingroup$ How can we simplify that $a_{n-1}-a_{n-2} + a_{n-3}+2(2n-3)=(n-1)^2-(n-2)^2 + (n-3)^2+2(2n-3)$? $\endgroup$ – MathBear Nov 24 '17 at 0:48
  • $\begingroup$ Try expanding the right hand side and cancel out terms. Potential useful formula $(a-b)^2=a^2-b^2-2ab$, $a^2-b^2=(a-b)(a+b)$. $\endgroup$ – Siong Thye Goh Nov 24 '17 at 0:49
  • $\begingroup$ I meant how did you get to $(n-1)^2$ from $a_{n-1}$? $\endgroup$ – MathBear Nov 24 '17 at 0:52
6
$\begingroup$

The second minus sign in the question should be a plus. $a_n = a_{n-1}-a_{n-2}\color{red}{+}a_{n-3} + 2(2n-3)$, it is then quite easy to show by using strong induction.

$\endgroup$
  • 3
    $\begingroup$ phew, you saved the day. $\endgroup$ – Siong Thye Goh Nov 24 '17 at 0:38
  • $\begingroup$ Sorry for the typo, my bad. How could I solve it though? $\endgroup$ – MathBear Nov 24 '17 at 0:40
  • 2
    $\begingroup$ Sorry, its correct. $\endgroup$ – Rene Schipperus Nov 24 '17 at 0:47
  • $\begingroup$ $1-4+9-6=0$ ... I get the constant term cancelling out ... as required. @ReneSchipperus $\endgroup$ – Donald Splutterwit Nov 24 '17 at 0:49
  • $\begingroup$ wolfram alpha verification Awesome correction. $\endgroup$ – Siong Thye Goh Nov 24 '17 at 0:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.