1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Problem concering Lucas numbers

  1. Jul 22, 2010 #1
    1. The problem statement, all variables and given/known data

    Prove that

    L1 + 2L2 + 4L3 + 8L4 + ... + 2n-1L1 = 2nFn+1 -1.


    2. Relevant equations

    The Fibonacci numbers denoted by Fn is defined as follows:

    F1 = 1 , F2 = 1 , F3 = 2 , F4 = 3 , F5 = 5

    Fn = Fn-1 + Fn-2

    The Lucas numbers are defined as:

    Ln = Fn+1 + Fn-1


    3. The attempt at a solution

    I have attempted to solve this as follows (which I'm sure is wrong):

    Assume it's true for n = k and for k + 1:

    2kFk+1 -1 + 2k+1Lk+1

    =>

    2kFk+1 + 2k+1(Fk+2 + Fk)

    =>

    2k(Fk+1 + 2(Fk+2 + Fk))

    But from here, I'm not quite sure how to proceed (if this is in fact, which i doubt, the right way to approach this problem).

    Also, note that I'm quite inexperienced when it comes to number theory so this may in fact be a trivially easy problem, but I'm having a hard time to see how to correctly approach these types of problems.

    Thanks in advance!
     
  2. jcsd
  3. Jul 22, 2010 #2

    Mark44

    Staff: Mentor

    I believe that your general approach is correct (i.e., using induction), but you're going about this incorrectly.
    No.
    1. Show that the proposition is true for a base case (n = 1).
    2. Assume that the proposition is true for n = k.
    3. Use the assumption of step 2 (the induction hypothesis) to show that the proposition is true for n = k + 1.
    No. None of these expressions "implies" any of the others. Each expression has a value. You should be working with equations, not expressions.
     
  4. Jul 22, 2010 #3
    Oh I see.

    How about this:

    1) Show that the proposition is true for n = 1:

    L1 = 1

    2F2 - 1 = 1

    =>

    L1 = 2F2 - 1

    2) Assume it is true for n = k

    3) Use induction to prove it's true for n = k + 1:

    If we add 2(k+1)-1Lk+1 to both sides we get:

    L1 + 2L2 + 4L3 + 8L4 + ... + 2k-1Lk + 2(k+1)-1Lk+1 = 2kFk+1 -1 + 2(k+1)-1Lk+1

    Rewriting the Lucas number on the RHS as Fibonacci numbers and simplifying we get:

    2kFk+1 -1 + 2k(Fk+2 + Fk)

    2k(Fk + Fk+1 + Fk+2) - 1

    2k(2Fk+3) - 1

    2k+1Fk+3 - 1

    As desired.

    Is this correct or at least an improvement on my previous reasoning?
     
  5. Jul 22, 2010 #4

    Mark44

    Staff: Mentor

    You skipped this. What equation do you have when n = k?
    Both sides of what?
    How are the expressions below connected with L1 + 2L2 + 4L3 + 8L4 + ... + 2k-1Lk + 2(k+1)-1Lk+1?
    What do you have against writing '='? What is desired is that you end up with an equation; namely
    L1 + 2L2 + 4L3 + 8L4 + ... + 2k-1Lk + 2(k+1)-1Lk+1 = 2k+1Fk+3 - 1.

    I haven't checked your work. At this point I'm just pointing out the holes in your work.
     
  6. Jul 22, 2010 #5
    Hello Mark44. Thanks for taking your time and helping me out with this one.

    Oh, I forgot to actually write that out. Sorry. I meant that if n = k we have:

    L1 + 2L2 + 4L3 + 8L4 + ... + 2k-1Lk = 2kFk+1 -1

    Of the original equation, i.e:

    L1 + 2L2 + 4L3 + 8L4 + ... + 2k-1Lk = 2kFk+1 -1

    The below expressions are the right hand side of the equation

    L1 + 2L2 + 4L3 + 8L4 + ... + 2k-1Lk + 2(k+1)-1Lk+1 = 2kFk+1 -1 + 2(k+1)-1Lk+1


    I realize that i forgot to write out the final equation. I only wrote out the right hand side because that was the part i kinda needed help with, i accidentally omitted the LHS of the equation.

    I also realize that I made a typo in my 2nd post. It was supposed to be 2k+1Fk+2 instead of 2k+1Fk+3.

    The final equation i got was the following:

    L1 + 2L2 + 4L3 + 8L4 + ... + 2k-1Lk + 2kLk+1 = 2k+1Fk+2 - 1

    Which I think is correct.

    Thanks for your help!
     
  7. Jul 22, 2010 #6

    Mark44

    Staff: Mentor

    Added = between the expressions below.
    How do you get the last expression, above? Fk + Fk+1 = Fk+2, certainly, but I don't see that Fk + Fk+1 + Fk+2 = 2Fk+3.

    As a counterexample, with F1 = 1, F2 = 2, F3 = 3, and F4 = 5,
    F1 + F2 + F3 = 1 + 2 + 3 = 6 [itex]\neq[/itex] 2F4 = 10.
     
  8. Jul 22, 2010 #7
    Yeah, that was my typo. I meant to say that Fk + Fk+1 + Fk+2 = 2Fk+2

    That is correct right? Because Fk + Fk+1 = Fk+2 and Fk+2 + Fk+2 = 2Fk+2?
     
  9. Jul 22, 2010 #8

    Mark44

    Staff: Mentor

    OK, that makes sense. I also missed what you said about the typo in post 2.
     
  10. Jul 22, 2010 #9
    No problem at all Mark44.

    Thanks a lot for your help, I really appreciate it!
     
  11. Jul 22, 2010 #10

    Mark44

    Staff: Mentor

    Sure, you're welcome!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Problem concering Lucas numbers
  1. Gauss Lucas Theorem (Replies: 6)

Loading...