# Homework Help: Problem concering Lucas numbers

1. Jul 22, 2010

### Srumix

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.

2. Jul 22, 2010

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

3. Jul 22, 2010

### Srumix

Oh I see.

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?

4. Jul 22, 2010

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

5. Jul 22, 2010

### Srumix

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!

6. Jul 22, 2010

### 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 $\neq$ 2F4 = 10.

7. Jul 22, 2010

### Srumix

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?

8. Jul 22, 2010

### Staff: Mentor

OK, that makes sense. I also missed what you said about the typo in post 2.

9. Jul 22, 2010

### Srumix

No problem at all Mark44.

Thanks a lot for your help, I really appreciate it!

10. Jul 22, 2010

### Staff: Mentor

Sure, you're welcome!