0
$\begingroup$

Show that, for all natural numbers m and n, we have 2Fm+n = FmLn + FnLm, where F0, F1, ... are the Fibonacci numbers and L0, L1, ... are the Lucas numbers.

The recurrence relation for Fibonacci sequence is: Fn = Fn-1 + Fn-2 where F0 = 0 and F1 = 1 The recurrence relation for Lucas sequence is: Ln = Ln-1 + Ln-2 where L0 = 2 and L1 = 1

$\endgroup$
0
$\begingroup$

Induction on $m$ and $n$ at the same time. Need two starting points (two stepping points for each recurrence).

  • Bases: $m + n = 0$ gives $m = n = 0$, or $2 F_0 = L_0 F_0 + L_0 F_0$, which checks out. Similarly, $m + n = 1$ is either $m = 0$, $n = 1$ or $m = 1$, $n = 0$. Both lead to $2 F_1 = L_0 F_1 + L_1 F_0$, which also checks out.
  • Induction: Suppose it is valid for $m + n$ and $m + n + 1$, so that: \begin{align} 2F_{m + n} &= L_m F_n + L_n F_m \\ 2F_{m + n + 1} &= L_m F_{n + 1} + L_{n + 1} F_m \\ &= L_{m + 1} F_n + L_n F_{m + 1} \end{align} Add the first to both versions of the second, on the LHS you get $2 F_{n + m + 2}$, the RHSs factor into $L_m (F_n + F_{n + 1}) + F_m (L_n + L_{n + 1}) = L_m F_{n + 2} + L_{n + 2} F_m$ and similarly $L_{m + 2} F_n + L_n F_{m + 2}$.
$\endgroup$

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.