Proof of the identity $F_{(n+1)k}=\frac{F_{2k}}{F_k}F_{nk}+(-1)^{k+1}F_{(n-1)k}\quad\forall k,n\in\mathbb{N}$

Question

I'm reading the solution to an exercise I have been given in which they use the identity $$F_{(n+1)k}=\frac{F_{2k}}{F_k}F_{nk}+(-1)^{k+1}F_{(n-1)k}\quad\forall k,n\in\mathbb{N}$$ where $F_n$ denotes the $n$th Fibonacci number. Is this a commonly known identity? Is there any way to obtain this identity in a relatively straightforward manner?

Answer 1

One way to get the identity mentioned in a comment by @ThorWittich is to observe that $$ \pmatrix{F_{n+1}&F_n\\F_n&F_{n-1}}=\pmatrix{1&1\\1&0}^n $$ from where it follows that $$ \pmatrix{F_{n+k+1}&F_{n+k}\\F_{n+k}&F_{n+k-1}}=\pmatrix{1&1\\1&0}^k\pmatrix{1&1\\1&0}^n =\pmatrix{F_{k+1}&F_k\\F_k&F_{k-1}}\pmatrix{F_{n+1}&F_n\\F_n&F_{n-1}} \\ =\pmatrix{F_{k+1}F_{n+1}+F_kF_n&F_{k+1}F_n+F_kF_{n-1}\\ F_kF_{n+1}+F_{k-1}F_n&F_kF_n+F_{k-1}F_{n-1}} $$ Now take one of the off-diagonal identities and change $k$ to $-k$ and remember that $F_{-k}=(-1)^{k-1}F_k$. \begin{align} F_{n+k}&=F_{k+1}F_n+F_kF_{n-1}\\ (-1)^kF_{n-k}&=F_{k-1}F_n-F_kF_{n-1}\\ \hline F_{n+k}+(-1)^kF_{n-k}&=(F_{k+1}+F_{k-1})F_n \end{align} Now read the last equation again for $n=k$ to get $$ F_{2k}=(F_{k+1}+F_{k-1})F_k $$ to conclude $$ (F_{n+k}+(-1)^kF_{n-k})F_k=F_{2k}F_n. $$ Next replace $n$ with $nk$ to get $$ F_{(n+1)k}=\frac{F_{2k}}{F_k}F_{nk}+(-1)^{k+1}F_{(n-1)k} $$ as claimed.

Answer 2

It is a commonly known identity. It follows directly from a slightly more general one: $$ F_{n+k}+(-1)^{k}F_{n-k}=L_{k}F_{n} $$ where $L_k$ is the $k$-th Lucas number. One of their properties is $F_{2k}=L_{k}F_{k}$.

Answer 3

$$ \varphi = \frac{1+\sqrt5}{2}$$ $$ F_n = \frac{\varphi^n +(-1)^{n+1}\cdot \varphi^{-n}}{\sqrt5} $$

Example: $$ F_{13} = \frac{\varphi^{13} + \varphi^{-13}}{\sqrt5} = 233 $$ Then: $$ \frac{F_{2k}}{F_k}=\frac{\frac{\varphi^{2k} +(-1)^{2k+1}\cdot \varphi^{-2k}}{\sqrt5}}{\frac{\varphi^k +(-1)^{k+1}\cdot \varphi^{-k}}{\sqrt5}} = \frac{\varphi^{2k} +(-1)^{2k+1}\cdot \varphi^{-2k}}{\varphi^{k} +(-1)^{k+1}\cdot \varphi^{-k}} =$$ $$ \frac{\varphi^{2k} - (-\varphi)^{-2k}}{\varphi^{k} - (-\varphi)^{-k}} = \varphi^{k} + (-\varphi^{-1})^{k}$$ and set: $$ \varphi^k = a $$ $$ (-\varphi^{-1})^k = b $$ $$ G_n = F_{kn} = \frac{a^n - b^n}{\sqrt5} $$ Test: $$ G_{n+1} = \frac {G_2}{G_1}G_n-(-1)^kG_{n-1}$$

$$ G_{n+1} + (-1)^kG_{n-1} = \frac {G_2}{G_1}G_n$$

$$ \frac{a^{n+1} - b^{n+1}}{\sqrt5} + (-1)^k\frac{a^{n-1} - b^{n-1}}{\sqrt5} = (a+b)\frac{a^n - b^n}{\sqrt5}$$

$$ a^{n+1} - b^{n+1}+ (-1)^k(a^{n-1} - b^{n-1}) = (a+b)(a^n - b^n)$$

$$ a^{n+1} - b^{n+1}+ (-1)^k(a^{n-1} - b^{n-1}) = a^{n+1} - b^{n+1} + ba^n - ab^n$$

$$ (-1)^k(a^{n-1} - b^{n-1}) = ba^n - ab^n $$

$$ (-1)^k(a^{n-1} - b^{n-1}) = ab(a^{n-1} - b^{n-1}) $$

$$ (-1)^k = ab \lor a^{n-1} - b^{n-1} = 0 $$

But:

$$ ab = \varphi^k \cdot (-\varphi^{-1})^k = \varphi^k \cdot \varphi^{-k} \cdot (-1)^k = (-1)^k $$

Demostrated.