= Solution
For the <Fibonacci addition formula>, use <mathematical induction> on $k$, with the assertion applying to every $n\ge1$. At $k=2$, $F_{n+2}=F_{n+1}+F_n=F_2F_{n+1}+F_1F_n$. If the formula holds for some $k\ge2$ and all $n$, apply it at $n+1$ and use the <Fibonacci number> recurrence:
$$
\begin{aligned}
F_{n+k+1}
&=F_kF_{n+2}+F_{k-1}F_{n+1}\\
&=F_k(F_{n+1}+F_n)+F_{k-1}F_{n+1}\\
&=F_{k+1}F_{n+1}+F_kF_n.
\end{aligned}
$$
This is the assertion at $k+1$, completing the <mathematical induction>. Thus
$$
\boxed{F_{n+k}=F_kF_{n+1}+F_{k-1}F_n\quad(n\ge1,\ k\ge2).}
$$
Taking $k=n\ge2$ gives the doubling identity
$$
\boxed{F_{2n}=F_n(F_{n+1}+F_{n-1})=F_nL_n.}
$$
For the <Lucas numbers>, $L_2=F_3+F_1=3$, and $L_3=F_4+F_2=4=L_2+L_1$. For $n\ge4$, both expressions for earlier <Lucas numbers> are available, and
$$
L_{n-1}+L_{n-2}
=(F_n+F_{n-2})+(F_{n-1}+F_{n-3})
=F_{n+1}+F_{n-1}=L_n.
$$
Hence $\boxed{L_1=1,\quad L_2=3,\quad L_n=L_{n-1}+L_{n-2}\ (n\ge3)}$. The separate $n=3$ check matters because the defining expression for $L_1$ was given separately.
The <Euclidean algorithm> and the <Fibonacci number> recurrence give, for $n\ge2$,
$$
\gcd(F_n,F_{n+1})=\gcd(F_n,F_{n-1}).
$$
Repeating reduces to $\gcd(F_2,F_1)=1$; the case $n=1$ is immediate. Therefore $\boxed{\gcd(F_n,F_{n+1})=1\ (n\ge1)}$.
For $n\ge2$, $L_n=F_n+2F_{n-1}$, so a common divisor $d$ of $F_n,L_n$ divides both $F_n$ and $2F_{n-1}$. Since $F_n,F_{n-1}$ are coprime, <Bézout's identity> gives integers $s,t$ with $sF_n+tF_{n-1}=1$. Multiplying by $2$ shows $d\mid2$. Conversely any common divisor of $F_n$ and $2$ divides $L_n$. Including $n=1$, this proves the stronger <greatest common divisor> identity
$$
\boxed{\gcd(F_n,L_n)=\gcd(F_n,2)\le2\quad(n\ge1).}
$$
Back to article page
