Proving $\sum_{j=0}^n (-1)^j {n \choose j} F_{s+2n-2j} = F_{s+n} $, where $F_n$ is the $n$-th Fibonacci number

Question

$$\sum_{j=0}^n (-1)^j {n \choose j} F_{s+2n-2j} = F_{s+n} $$

($F$ is Fibonacci number).

I have been trying to prove this by mathematical induction. First I assume this is true for n. If I could prove it works for n+1, then it is done. $\sum_{j=0}^{n+1} (-1)^j {n+1 \choose j} F_{s+2n-2j+2} = F_{s+n+1} $ Also I could replace s with s+1 since it is valid for general constant s. So I could get $\sum_{j=0}^n (-1)^j {n \choose j} F_{s+1+2n-2j} = F_{s+1+n} $

Answer 1

Note that $$\sum_{j=0}^n\,(-1)^j\,\binom{n}{j}\,z^{s+2(n-j)}=z^s\,\sum_{j=0}^n\,\binom{n}{j}\,(-1)^j\,\left(z^2\right)^{(n-j)}\,.$$ Using the Binomial Theorem, $$\sum_{j=0}^n\,(-1)^j\,\binom{n}{j}\,z^{s+2(n-j)}=z^s\,\big((-1)+z^2\big)^n=z^s\,\left(z^2-1\right)^n\,.$$ If $z$ satisfies $z^2-z-1=0$, then $z\in\{\omega,\bar{\omega}\}$, where $\omega:=\frac{1+\sqrt{5}}{2}$ and $\bar{\omega}:=\frac{1-\sqrt{5}}{2}$. Observe that $z^2-1=z$ for $z\in\{\omega,\bar{\omega}\}$, whence $$\sum_{j=0}^n\,(-1)^j\,\binom{n}{j}\,z^{s+2(n-j)}=z^s\,\left(z^2-1\right)^n=z^s\,z^n=z^{s+n}\text{ for }z\in\{\omega,\bar{\omega}\}\,.$$

Note that the $k$-th Fibonacci number $F_k$ is given by $$F_k=\frac{\omega^k-\bar{\omega}^k}{\omega-\bar\omega}\text{ for }k=0,1,2,\ldots\,.$$ This proves that $$\begin{align}\sum_{j=0}^n\,(-1)^j\,\binom{n}{j}\,F_{s+2(n-j)}&=\sum_{j=0}^n\,(-1)^j\,\binom{n}{j}\,\left(\frac{\omega^{s+2(n-j)}-\bar{\omega}^{s+2(n-j)}}{\omega-\bar{\omega}}\right) \\ &=\frac{1}{\omega-\bar\omega}\,\small\left(\sum_{j=0}^n\,(-1)^j\,\binom{n}{j}\,\omega^{s+2(n-j)}-\sum_{j=0}^n\,(-1)^j\,\binom{n}{j}\,\bar{\omega}^{s+2(n-j)}\right) \\ &=\frac{1}{\omega-\bar\omega}\,\left(\omega^{s+n}-\bar{\omega}^{s+n}\right)=F_{s+n}\,. \end{align}$$

---

Alternatively, define the left-shift operator $S$ on any real- or complex-valued sequence $\left(a_k\right)_{k\in\mathbb{Z}_{\geq 0}}$ by $$(Sa)_k:=a_{k+1}\text{ for all }k=0,1,2,\ldots\,.$$ For an operator $T$, we define $T^0$ to be the identity operator $I$ (namely, $(Ia)_k:=a_k$ for all $k=0,1,2,\ldots$), and $$\left(T^ra\right)_k:=\big(T\left(T^{r-1}a\right)\big)_k$$ for $r\in\mathbb{Z}_{\geq 1}$ and $k=0,1,2,\ldots$. Now, the $2$-step forward difference $\Delta_2$ is defined to be $\Delta_2:=S^2-I$; that is, $$(\Delta_2 a)_k=(S^2a)_k-(Ia)_k=a_{k+2}-a_k\text{ for each }k=0,1,2,\ldots\,.$$ In particular, $$(\Delta_2 F)_k=F_{k+2}-F_k=F_{k+1}=(SF)_k\text{ for each }k=0,1,2,\ldots\,.$$ In other words, $\Delta_2$ acts the same way as $S$ on the Fibonacci sequence.

The hint is to show that $$\Delta_2^n=\sum_{j=0}^n\,(-1)^j\,\binom{n}{j}\,S^{2(n-j)}\,,$$ which gives $$(\Delta_2^n F)_s=\sum_{j=0}^n\,(-1)^j\,\binom{n}{j}\,F_{s+2(n-j)}$$ for any $s,n\in\mathbb{Z}_{\geq 0}$. Since $\Delta_2$ acts like $S$ on the Fibonacci sequence, and $\Delta_2$ and $S$ are commuting operators, we can then conclude that $$(\Delta_2^n F)_s=(S^nF)_s=F_{n+s}\,.$$

Answer 2

Here is a proof by induction over $n$. To recap, we want to show $$F_{s+n} = \sum_{j=0}^n (-1)^j \binom{n}{j} F_{s+2n-2j} \tag{1}$$ The base case, $n=0$, is trivial. So suppose (1) holds for some value of $n$. We want show it holds for $n+1$. Since $s$ is arbitrary, we may substitute $s+1$ for $s$ in (1): $$F_{s+n+1} = \sum_{j=0}^n (-1)^j \binom{n}{j} F_{s+1+2n-2j}$$ Next, we apply the Fibonacci identity $F_{n} = F_{n+1}-F_{n-1}$: $$F_{s+n+1} = \sum_{j=0}^n (-1)^j \binom{n}{j} (F_{s+2+2n-2j}-F_{s+2n-2j})$$ So $$\begin{align} F_{s+n+1} &= \sum_{j=0}^n (-1)^j \binom{n}{j} F_{s+2+2n-2j} - \sum_{j=0}^n (-1)^j \binom{n}{j} F_{s+2n-2j} \\ &= F_{s+2+2n} + \sum_{j=1}^n (-1)^j \binom{n}{j} F_{s+2+2n-2j} - \sum_{j=0}^{n-1} (-1)^j \binom{n}{j} F_{s+2n-2j} - (-1)^n F_s \\ &= F_{s+2+2n} + \sum_{j=1}^n (-1)^j \binom{n}{j} F_{s+2+2n-2j} - \sum_{j=1}^{n} (-1)^{j-1} \binom{n}{j-1} F_{s+2+2n-2j} - (-1)^n F_s \tag{2}\\ &= F_{s+2+2n} + \sum_{j=1}^n (-1)^j \left[ \binom{n}{j} + \binom{n}{j-1} \right] F_{s+2+2n-2j} +(-1)^{n+1}F_s \\ &= F_{s+2+2n} + \sum_{j=1}^n (-1)^j \binom{n+1}{j} F_{s+2+2n-2j} +(-1)^{n+1}F_s \tag{3}\\ &= \sum_{j=0}^{n+1} (-1)^j \binom{n+1}{j} F_{s+2(n+1)-2j} \end{align}$$

This completes the proof by induction.

Notes

(2) Shifting the index in the second sum

(3) Applying the recursive formula for binomial coefficients