Here's the question you clicked on:
KingGeorge
[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}\)
The recurrence relation seems pretty messy, so I will try to solve it inductively, T_T
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?
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.
I would suggest induction as bmp is attempting.
@bmp, check your value for \(a_7\)
I think every \[a_{n} = Fib(n)*Fib(n)\]that is a perfect square for every n in N.
But how are you going to prove it?
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.
\[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.
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 :-(
I'm also pretty sure what you just did was a fallacy. However, induction is the correct path to go. Keep trying.
Another hint that may be helpful: Use strong induction.
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.
You are also correct in that it is the sequence of squares of the Fibonacci numbers. You still need to prove it though. :)
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?
Yeah, I just now got to it. I think that would be the way, if you can prove for a(1)...a(k).
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?
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.
@m_charron2 Kudos for beating me on the proof, mate :-). Well done.
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...
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.
For those interested, here's the solution I got when I was challenged with this problem.
on this note, off to sleep for me, that drained me lol. Excellent problem KingGeorge!