Show that, for all natural numbers m and n, we have 2Fm+n = FmLn + FnLm

Question

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

Answer 1

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