[SOLVED] Define a sequence of real numbers by \(a_0=0\), \(a_1=1\), \(a_2=1\) and \[\large a_{n+3}=2a_{n+2}+2a_{n+1}-a_n\]Show that \(a_n\) is a perfect square for every \(n\in\mathbb{N}\)

- KingGeorge

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- jamiebookeater

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- anonymous

The recurrence relation seems pretty messy, so I will try to solve it inductively, T_T

- anonymous

How about if we reduce every term into the \(ka_{n+2} + ma_{n+1} + na_n\)?
The term \(a_n\) won't matter as its Zero. We can express terms as just \(k + m\). Maybe?

- anonymous

For n=0.

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- anonymous

I tried to find a pattern in the roots, but couldn't. a3 = 2*2, a4 = 3*3, a5 = 5*5, a6 = 8*8, a7 = 12*12. Will try something else now.

- KingGeorge

I would suggest induction as bmp is attempting.

- KingGeorge

@bmp, check your value for \(a_7\)

- anonymous

Ah, got it, I think.

- anonymous

Thanks @KingGeorge :-)

- anonymous

Fibonacci it is, then :-)

- anonymous

Fibonacci How?

- anonymous

I think every
\[a_{n} = Fib(n)*Fib(n)\]that is a perfect square for every n in N.

- anonymous

But how are you going to prove it?

- anonymous

I am trying to refine my proof, but I think that assuming that that is true(by induction), it's not too hard to proof that it is correct.

- anonymous

to prove*

- anonymous

\[a_{n+3} = 2a_{n+2} + 2a_{n+1} -a_n\]Lets assume \(a_{n+3} = q^2\).
\[a_{n+4} = 2a_{n+3} + 2a_{n+2} -a_{n+1} \implies a_{n+4} = 2q^2 + 2a_{n+2}-a_{n+1}\]Now what? How do we prove \(a_{n+4}\) is perfect square as well.

- anonymous

I think that the proof would go more or less like this:
Assume:\[a_{k} = Fib(k)*Fib(k)\]Clearly, that holds for k <= 2. So, multiply it by -1, we get:\[-a_{k} = -(Fib(k)*Fib(k))\]Add 2*(ak+2 ak+1) in both sides, we get:\[2(a_{k+2} + a_{k+1}) - a_{k} = 2(a_{k+2} + a_{k+1}) - Fib(k)Fib(k) \rightarrow a_{k+3} = a_{k+3}\]What I just did I am pretty sure is a fallacy, but the idea is that we have to prove that every {ak} has the form Fib^2(k). I am still working on it, was never good with proofs :-(

- KingGeorge

I'm also pretty sure what you just did was a fallacy. However, induction is the correct path to go. Keep trying.

- KingGeorge

Another hint that may be helpful:
Use strong induction.

- anonymous

I see. It makes sense, since I will need a(1) ... a(k) to be true to prove that a(k+1) is true. This is a nice problem @KingGeorge :-) Thanks for it.

- KingGeorge

You are also correct in that it is the sequence of squares of the Fibonacci numbers. You still need to prove it though. :)

- anonymous

I think I may have gotten it?
a5 = 2a4 + 2a3 - a2 = 2 F(4) ^2 + 2 F(3) ^2 - F(2) ^2
= F(4)^2 + 2F(3)^2 +(F(3)+F(2))^2 - F(2)^2
= F(4)^2 + 2F(3)^2 +F(3)^2+2F(3)F(2)
= F(4)^2 + 2F(3)(F(3)+F(2)) + F(3)^2
= (F(4) + F(3))^2
= (F(5)^2)
and this would be true always?
tadam?

- anonymous

Yeah, I just now got to it. I think that would be the way, if you can prove for a(1)...a(k).

- anonymous

well, I guess that, if a4 = F(4)^2 and a5 = F(5)^2, then a6 = F(6)^2, so a7 = F(7)^2, so a8 = F(8)^2, etc? Am I allowed to do this?

- KingGeorge

Try using n, n+1, n+2, n+3 instead of 4, 5, 6, 7. Your proof above is very very close to correct. You basically just have to use a variable instead of numbers.

- anonymous

@m_charron2 Kudos for beating me on the proof, mate :-). Well done.

- anonymous

oh, couldn't've done it if you hadn't told us about the fibonacci here, so Kudos to you as well
I can't find how to start replacing the numbers with variables without assuming things. I can't prove that a_(n+3) = F(n+3)^2 without first knowing that a_(n+2) = F(n+2)^2, a_(n+1) = F(n+1)^2 and a_n = F(n)^2... I'm lost in a mental paradox of my own making I think...

- KingGeorge

You're first method of showing it's true for \(a_5\) is so close it might as well be correct. Just substitute \[\large a_5 =a_{n+1}\]\[\large a_4 =a_{n}\]\[\large a_3 =a_{n-1}\]\[\large a_2 =a_{n-2}\]And similar substitutions for the Fibonacci numbers. Then go through the same steps. You will then have proved it for the general case.

- KingGeorge

For those interested, here's the solution I got when I was challenged with this problem.

##### 1 Attachment

- anonymous

on this note, off to sleep for me, that drained me lol. Excellent problem KingGeorge!

- KingGeorge

Good night.

Looking for something else?

Not the answer you are looking for? Search for more explanations.