Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

KingGeorge

  • 4 years ago

[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}\)

  • This Question is Closed
  1. bmp
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  2. Ishaan94
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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?

  3. Ishaan94
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    For n=0.

  4. bmp
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  5. KingGeorge
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 4

    I would suggest induction as bmp is attempting.

  6. KingGeorge
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 4

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

  7. bmp
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ah, got it, I think.

  8. bmp
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks @KingGeorge :-)

  9. bmp
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Fibonacci it is, then :-)

  10. Ishaan94
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Fibonacci How?

  11. bmp
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  12. Ishaan94
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    But how are you going to prove it?

  13. bmp
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  14. bmp
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    to prove*

  15. Ishaan94
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    \[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.

  16. bmp
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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 :-(

  17. KingGeorge
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 4

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

  18. KingGeorge
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 4

    Another hint that may be helpful: Use strong induction.

  19. bmp
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  20. KingGeorge
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 4

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

  21. m_charron2
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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?

  22. bmp
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  23. m_charron2
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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?

  24. KingGeorge
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 4

    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.

  25. bmp
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  26. m_charron2
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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...

  27. KingGeorge
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 4

    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.

  28. KingGeorge
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 4

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

  29. m_charron2
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  30. KingGeorge
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 4

    Good night.

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

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy