Discrete Fibonacci sequence problem

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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