Fibonacci addition formula ($F_{n+k}=F_k{F}_{n+1}+F_{k-1}{F}_n$)

With the standard Fibonacci numbers $F_0=0$, $F_1=1$, this identity holds for $n\ge 0$, $k\ge 1$. At $k=1$ it is immediate. If it holds for $k$ at every $n$, apply it at $n+1$ and use $F_{n+2}=F_{n+1}+F_n$ to obtain $F_{n+k+1}=F_{k+1}{F}_{n+1}+F_k{F}_n$, proving the assertion by mathematical induction. Taking $k=n$ gives $F_{2n}=F_n(F_{n+1}+F_{n-1})$ for $n\ge 1$, linking the doubling formula to the Lucas numbers.

Consecutive Fibonacci numbers are coprime by the Euclidean algorithm. The Fibonacci addition formula writes $F_m=F_{m-n}{F}_{n+1}+F_{m-n-1}{F}_n$ for $m>n$. Taking the greatest common divisor with $F_n$ removes the last summand, and multiplication by the coprime factor $F_{n+1}$ leaves that gcd unchanged. The case $m=n$ uses $F_0=0$. Applying the Euclidean algorithm to the indices yields the strong-divisibility identity $\gcd (F_m,F_n)=F_{\gcd (m,n)}$ for nonnegative indices, with the usual zero conventions.