3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

You need to use strong induction in this case, i.e., prove the base case(s) and then assume it's true for all cases less than some limit. Note, however, that the # of base cases to prove must be at least the # you will directly reference in your proof.

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.

$\endgroup$
  • $\begingroup$ Thank you for the reply! So basically I just need to do induction as usual, but instead of assuming ( *) is only true for k I must assume it's true for 0,1,2... k. Is that correct? Is there any way to prove ( *) by normal induction instead of strong induction? $\endgroup$ – Hang Nguyen Apr 21 at 0:01
  • $\begingroup$ @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. $\endgroup$ – John Omielan Apr 21 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.