# How to prove the equality $a_n = n^2$ for every $n$, if $n \in \mathbb N$?

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?

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.

• There must be something wrong with the question since that expression is not $n^2$. – Rene Schipperus Nov 24 '17 at 0:36
• Hmm.... you are right. The coefficient of $n^2$ is $-n^2$ – Siong Thye Goh Nov 24 '17 at 0:38
• 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)$? – MathBear Nov 24 '17 at 0:48
• 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)$. – Siong Thye Goh Nov 24 '17 at 0:49
• I meant how did you get to $(n-1)^2$ from $a_{n-1}$? – MathBear Nov 24 '17 at 0:52

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.

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