# fibonacci and lucas numbers induction

I'm having trouble proving by induction that this following Fibonacci-Lucas equation

$$F_{2n+k} = F_n L_{n+k} + (-1)^n F_k \tag{*}$$

is true, given that

$$F_{2n} = F_nL_n$$

and

$$F_{2n+1} = F_nL_{n+1} + (-1)^n$$

are true.

I did the base case $$k = 1$$, but I can't prove the induction step for $$k+1$$. In particular, my textbook said I have to assume (*) is true for $$k$$ and prove it for $$k+1$$, but I cannot prove it without assuming (*) is true for $$k$$ AND $$k-1$$.

Can someone help me? This is the first time I'm posting so I'm sorry if there's anything wrong.

Using this variant in your case, you first need to prove the base cases of $$k = 0$$ and $$k = 1$$, which are true using what you're allowed to assume about $$F_{2n}$$ and $$F_{2n+1}$$, plus given that $$F_0 = 0$$ and $$F_1 = 1$$. Thus, assume that (*) is true for all $$k$$ from $$0$$ to some integer $$m \ge 1$$. Now, you can try to prove (*) for $$k = m + 1$$ given it's true for $$k = m$$ and $$k = m - 1$$. Since your question indicates that this is the issue which was preventing you from completing the induction, I assume you can do the rest yourself & won't give a solution to it here.
• @HangNguyen You're welcome. Yes, as I stated, you just need to assume it's true from $0$ to some $m \ge 1$. The problem with trying to prove (*) using normal induction instead is you are quite limited if you can only assume the previous value. Also, since both Fibonacci and Lucas definitions involve the sum of the previous $2$ values, you likely can't use them but, instead, must use the direct definitions of what the $F_n$ & $L_n$ values. However, not only will this be more difficult, but you won't even need induction then. Nonetheless, you may wish to check it further anyway to verify this. – John Omielan Apr 21 '19 at 0:21