Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The Fibonacci sequence satisfies $F_0 = F_1 = 1$ and the recurrence relation $F_k=F_{k-1}+F_{k-2}$ for all integers $k\geq 2$. Prove that $F_k+2F_k-F_{2k+1}= (-1)^k$ for all integers $k\geq 0$.

share|improve this question
4  
Try mathematical induction. BTW: if it's a homework problem, please tag it. –  GWu Apr 11 '11 at 0:47
1  
What have you tried? –  Matthew Conroy Apr 11 '11 at 1:36
    
Write the recurrence relation in matrix form: en.wikipedia.org/wiki/Fibonacci_number#Matrix_form –  lhf Apr 11 '11 at 10:39
add comment

3 Answers 3

I think... you have made a mistake writing down the problem.

First: Usually Fibonacci numbers are defined f0 =0 , f1=1 (so they coincide with Binet's formula).

BUT, assume you actually want to get F0=1, F1=1 (you'll get the same sequence shifted by one position)

Then... notice that $F_k+2F_k =3F_k$ , so the fact that you don't collect that, hints of a possible mistake.

BUT, plug in some values, you get F3 = 3, F7=21 and your equation becomes $F_3 + 2F_3 -F_7 = 3 + 6 - 21 = -12$. So... your formula is just not true (that's why you're having problems proving it).

share|improve this answer
    
See my post...mymathforum.com/… - this may be a derivative result –  The Chaz 2.0 Apr 11 '11 at 2:52
add comment

I have gotten so far that when k= 0 both sides equal 1. when k = 1 both sides equal -1. When k= 2 both sides equal 1. however I am stuck when trying to figure out how to come up with an equation to explain this.

share|improve this answer
add comment

It usually helps if you have the right equation. My guess is $F_{k+1} (2 F_{k-1} + F_k) - F_{2k+1} = (-1)^k$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.