Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook