Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

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

  • 2 years ago
  • 2 years ago

  • This Question is Closed
  1. bmp
    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 years ago
  2. Ishaan94
    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?

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

    For n=0.

    • 2 years ago
  4. bmp
    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.

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

    I would suggest induction as bmp is attempting.

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

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

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

    Ah, got it, I think.

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

    Thanks @KingGeorge :-)

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

    Fibonacci it is, then :-)

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

    Fibonacci How?

    • 2 years ago
  11. bmp
    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.

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

    But how are you going to prove it?

    • 2 years ago
  13. bmp
    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.

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

    to prove*

    • 2 years ago
  15. Ishaan94
    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.

    • 2 years ago
  16. bmp
    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 :-(

    • 2 years ago
  17. KingGeorge
    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.

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

    Another hint that may be helpful: Use strong induction.

    • 2 years ago
  19. bmp
    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.

    • 2 years ago
  20. KingGeorge
    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. :)

    • 2 years ago
  21. m_charron2
    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?

    • 2 years ago
  22. bmp
    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).

    • 2 years ago
  23. m_charron2
    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?

    • 2 years ago
  24. KingGeorge
    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.

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

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

    • 2 years ago
  26. m_charron2
    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...

    • 2 years ago
  27. KingGeorge
    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.

    • 2 years ago
  28. KingGeorge
    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.

    • 2 years ago
  29. m_charron2
    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!

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

    Good night.

    • 2 years ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.