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 
$$\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} $
 A: 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}\,.$$
A: 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
