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

Question

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?

score 6 · Answer 1 · answered Nov 24 '17 at 00:37

6

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.

answered Nov 24 '17 at 00:37

Donald Splutterwit

36,613
2
26
73

3

phew, you saved the day. – Siong Thye Goh Nov 24 '17 at 00:38
Sorry for the typo, my bad. How could I solve it though? – MathBear Nov 24 '17 at 00:40
2

Sorry, its correct. – Rene Schipperus Nov 24 '17 at 00:47
$1-4+9-6=0$ ... I get the constant term cancelling out ... as required. @ReneSchipperus – Donald Splutterwit Nov 24 '17 at 00:49
wolfram alpha verification Awesome correction. – Siong Thye Goh Nov 24 '17 at 00:50

Siong Thye Goh · Accepted Answer · 2017-11-24T00:41:01.297

4

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.

edited Nov 24 '17 at 00:41

answered Nov 24 '17 at 00:34

Siong Thye Goh

149,520
20
88
149

2

There must be something wrong with the question since that expression is not $n^2$. – Rene Schipperus Nov 24 '17 at 00:36
Hmm.... you are right. The coefficient of $n^2$ is $-n^2$ – Siong Thye Goh Nov 24 '17 at 00: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 00: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 00:49
I meant how did you get to $(n-1)^2$ from $a_{n-1}$? – MathBear Nov 24 '17 at 00:52
I see, induction hypothesis, we are going to assume $a_k = k^2$ for all $k < n$. hence we have $a_{n-1}=(n-1)^2$. – Siong Thye Goh Nov 24 '17 at 00:53
Yes, that was the breaking point for me, thanks! – MathBear Nov 24 '17 at 01:07

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

2 Answers2