Problem concering Lucas numbers

[Srumix]

Homework Statement

Prove that

L₁ + 2L₂ + 4L₃ + 8L₄ + ... + 2^n-1L₁ = 2ⁿF_n+1 -1.

Homework Equations

The Fibonacci numbers denoted by F_n is defined as follows:

F₁ = 1 , F₂ = 1 , F₃ = 2 , F₄ = 3 , F₅ = 5

F_n = F_n-1 + F_n-2

The Lucas numbers are defined as:

L_n = F_n+1 + F_n-1

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:

2^kF_k+1 -1 + 2^k+1L_k+1

=>

2^kF_k+1 + 2^k+1(F_k+2 + F_k)

=>

2^k(F_k+1 + 2(F_k+2 + F_k))

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!

 

[Mark44]

Homework Statement

Prove that

L₁ + 2L₂ + 4L₃ + 8L₄ + ... + 2^n-1L₁ = 2ⁿF_n+1 -1.

Homework Equations

The Fibonacci numbers denoted by F_n is defined as follows:

F₁ = 1 , F₂ = 1 , F₃ = 2 , F₄ = 3 , F₅ = 5

F_n = F_n-1 + F_n-2

The Lucas numbers are defined as:

L_n = F_n+1 + F_n-1

The Attempt at a Solution

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

I believe that your general approach is correct (i.e., using induction), but you're going about this incorrectly.

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

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.

2^kF_k+1 -1 + 2^k+1L_k+1

=>

2^kF_k+1 + 2^k+1(F_k+2 + F_k)

=>

2^k(F_k+1 + 2(F_k+2 + F_k))

No. None of these expressions "implies" any of the others. Each expression has a value. You should be working with equations, not expressions.

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!

 

[Srumix]

Oh I see.

How about this:

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

L₁ = 1

2F₂ - 1 = 1

=>

L₁ = 2F₂ - 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)-1L_k+1 to both sides we get:

L₁ + 2L₂ + 4L₃ + 8L₄ + ... + 2^k-1L_k + 2^(k+1)-1L_k+1 = 2^kF_k+1 -1 + 2^(k+1)-1L_k+1

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

2^kF_k+1 -1 + 2^k(F_k+2 + F_k)

2^k(F_k + F_k+1 + F_k+2) - 1

2^k(2F_k+3) - 1

2^k+1F_k+3 - 1

As desired.

Is this correct or at least an improvement on my previous reasoning?

 

[Mark44]

Oh I see.

How about this:

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

L₁ = 1

2F₂ - 1 = 1

=>

L₁ = 2F₂ - 1

2) Assume it is true for n = k

You skipped this. What equation do you have when n = k?

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

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

Both sides of what?

L₁ + 2L₂ + 4L₃ + 8L₄ + ... + 2^k-1L_k + 2^(k+1)-1L_k+1 = 2^kF_k+1 -1 + 2^(k+1)-1L_k+1

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

How are the expressions below connected with L₁ + 2L₂ + 4L₃ + 8L₄ + ... + 2^k-1L_k + 2^(k+1)-1L_k+1?

2^kF_k+1 -1 + 2^k(F_k+2 + F_k)

2^k(F_k + F_k+1 + F_k+2) - 1

2^k(2F_k+3) - 1

2^k+1F_k+3 - 1

As desired.

What do you have against writing '='? What is desired is that you end up with an equation; namely
L₁ + 2L₂ + 4L₃ + 8L₄ + ... + 2^k-1L_k + 2^(k+1)-1L_k+1 = 2^k+1F_k+3 - 1.

I haven't checked your work. At this point I'm just pointing out the holes in your work.

Is this correct or at least an improvement on my previous reasoning?

 

[Srumix]

Hello Mark44. Thanks for taking your time and helping me out with this one.

You skipped this. What equation do you have when n = k?

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

L₁ + 2L₂ + 4L₃ + 8L₄ + ... + 2^k-1L_k = 2^kF_k+1 -1

Both sides of what?

Of the original equation, i.e:

L₁ + 2L₂ + 4L₃ + 8L₄ + ... + 2^k-1L_k = 2^kF_k+1 -1

How are the expressions below connected with L₁ + 2L₂ + 4L₃ + 8L₄ + ... + 2^k-1L_k + ^2(k+1)-1L_k+1?

The below expressions are the right hand side of the equation

L₁ + 2L₂ + 4L₃ + 8L₄ + ... + 2^k-1L_k + 2^(k+1)-1L_k+1 = 2^kF_k+1 -1 + 2^(k+1)-1L_k+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 2^k+1F_k+2 instead of 2^k+1F_k+3.

The final equation i got was the following:

L₁ + 2L₂ + 4L₃ + 8L₄ + ... + 2^k-1L_k + 2^kL_k+1 = 2^k+1F_k+2 - 1

Which I think is correct.

Thanks for your help!

 

[Mark44]

Added = between the expressions below.

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

2^kF_k+1 -1 + 2^k(F_k+2 + F_k)

= 2^k(F_k + F_k+1 + F_k+2) - 1

= 2^k(2F_k+3) - 1

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

As a counterexample, with F₁ = 1, F₂ = 2, F₃ = 3, and F₄ = 5,
F₁ + F₂ + F₃ = 1 + 2 + 3 = 6 \neq 2F₄ = 10.

= 2^k+1F_k+3 - 1

 

[Srumix]

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

Yeah, that was my typo. I meant to say that F_k + F_k+1 + F_k+2 = 2F_k+2

That is correct right? Because F_k + F_k+1 = F_k+2 and F_k+2 + F_k+2 = 2F_k+2?

 

[Mark44]

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

 

[Srumix]

No problem at all Mark44.

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

 

[Mark44]

Sure, you're welcome!