Binomial transform of fibonacci sequence is negated fibonacci sequence proof I'm trying to prove that the following relation holds
$$
\sum_{j=0}^n \binom{n}{j}(-1)^j F_j = -F_n
$$
Where $F_i$ denotes the $i$-th finonacci number. I'm currently trying an induction argument but I get stuck at
$$
\sum_{j=0}^n \binom{n}{j}(-1)^j F_j = (-1)^n F_n + \sum_{j=0}^{n-1} \binom{n}{j}(-1)^j F_j = (-1)^n F_n + \sum_{j=0}^{n-1} \binom{n}{j}(-1)^j F_{j-1} + \sum_{j=0}^{n-1} \binom{n}{j}(-1)^j F_{j-2} = 
$$
$$
= (-1)^n F_n + \sum_{j=0}^{n-1} \binom{n-1}{j}\frac{n}{n-j}(-1)^j F_{j-1} + \sum_{j=0}^{n-1} \binom{n}{j}\frac{n}{n-j}(-1)^j F_{j-2}
$$
I would like to find a way to apply the induction hypothesis on the expresion above but the term $n/(n-j)$ makes it difficult because it depends on $j$ so I can't get it out of the sum. I already know how to prove this relation using generating functions, but currently I need to solve the problem using induction. Thanks in advance for the help.
 A: Define the finite sum
$$
S(n,k) := \sum_{j=0}^n \binom{n}{j}(-1)^j F_{j+k}. \tag1
$$
Define  $\,T(n,k)\,$ by
$$ T(n,k) = -(-1)^k F_{n-k}. \tag2 $$
Note that by Fibonacci recursion
$$ T(n\!-\!1,k) - T(n\!-\!1,k\!+\!1) \!=\!
 -(-1)^k F_{n\!-\!k\!-\!1} \!+\!
  (-1)^k F_{n\!-\!k\!-\!2}\\
 = -(-1)^k(F_{n-k-2}+F_{n-k-1})=
-(-1)^k F_{n-k} = T(n,k). \tag3 $$
Use the definitions of $\,S(n,k) \,$ and $\,T(n,k),\,$ and
a property of Fibonacci to get
$$ S(0,k) = F_k = -(-1)^kF_{-k} = T(0,k). \tag4 $$
Temporarily define
$$ Q := S(n-1,k) \!-\! S(n-1,k+1). \tag5 $$
Use the definition $(1)$ of $\,S(n,k)\,$ to get
$$ Q =\sum_{j=0}^{n-1} \binom{n-1}{j}(-1)^j F_{j+k} -
\sum_{j=0}^{n-1} \binom{n-1}{j}(-1)^j F_{j+k+1}. \tag6 $$
Add a zero terms to both sums and reindex the second sum to get
$$ Q =\sum_{j=0}^n \binom{n-1}{j}(-1)^j F_{j+k} +
\sum_{j=0}^n \binom{n-1}{j-1}(-1)^j F_{j+k}. \tag7 $$
Combine the two binomial coefficients and use definition $(1)$ to get
$$ Q =\sum_{j=0}^n \binom{n}{j}(-1)^j F_{j+k} = S(n,k). \tag8 $$
Since both $\,S(n,k)\,$ and $\,T(n,k)\,$ satisfy the
same recursion $(3)$ and $(5)$ and initial values
$(4)$, by induction on $\,n\,$ they are equal.
This implies that
$$ S(n,0) = \sum_{j=0}^n \binom{n}{j}(-1)^j F_j =
 T(n,0) = -F_n. \tag{9} $$
That proves the result asked for.

It is interesting that $\,S(n,k) = -S(k,n)\,$ so the array
is skew symmetric. Also the array $\,(-1)^nS(n,k)\,$ which
is OEIS sequence A159864 is
the difference array of Fibonacci numbers.
A: Let $S_n$ be the sum in question. Our strategy will be to get a recurrence relation for $S_n$.
We start by applying Pascal's rule to each binomial coeffficient, and spliitting $S_n$ into two sums. We get
\begin{align}
S_n
&=\sum_j \binom{n-1}j(-1)^jF_j+\sum_j \binom{n-1}{j-1}(-1)^jF_j
\\&=S_{n-1}\hspace{1.24in}+\sum_j\binom{n-1}{j-1}(-1)^j F_j
\end{align}
We have made progress, since $S_{n-1}$ appeared, but we cannot express the remaining sum in terms of previous terms in the $(S_n)_{n\ge 0}$ sequence yet. To fix this, we need to split up the $F_j$'s in that sum using the Fibonacci recurrence:
$S_n$ into two sums. We get
\begin{align}
S_n
&=S_{n-1}+\sum_j\binom{n-1}{j-1}(-1)^j F_{j-1}+\sum_j\binom{n-1}{j-1}(-1)^j F_{j-2}
\\&=S_{n-1}-S_{n-1}+\sum_j\binom{n-1}{j-1}(-1)^j F_{j-2}
\\&=\sum_j\binom{n-1}{j-1}(-1)^j F_{j-2}
\end{align}
Finally, we expand $\binom{n-1}{j-1}$ using the hockey stick identity, via
$$
j\ge 2\quad \implies \quad \binom{n-1}{j-1}=\binom{n-2}{j-2}+\binom{n-3}{j-2}+\dots+\binom{0}{j-2}
$$
Applying this, the lower indices of all binomial coefficients are $j-2$, which matches the index of $F_{j-2}$. This allows us to write everything in terms of $S$:
\begin{align}
S_n
&=\underbrace{0}_{j=0\text{ term}}+
\underbrace{-1}_{j=1\text{ term}}+\sum_{j\ge 2}\binom{n-1}{j-1}(-1)^j F_{j-2}
\\&= -1+\sum_{j\ge 2}\left[\binom{n-2}{j-2}+\binom{n-3}{j-2}+\dots+\binom{0}{j-2}\right](-1)^j F_{j-2}
\\&=-1+S_{n-2}+S_{n-3}+\dots+S_0
\end{align}
Since $-F_n$ obeys the same recurrence, you can prove that $S_n=-F_n$ by induction. Namely, you can prove by induction easily that
$$
-F_n=-1+(-F_{n-2})+(-F_{n-3})+\dots+(-F_0)
$$
A: Not by induction as you request but, just for reference, I give a proof based on the Binet's formula, copied from here and then adjusted for your slightly different equality:
Remember that $F_n = \frac{1}{\sqrt5}\left(\varphi^n - (-\varphi)^{-n}\right)$ and $\varphi - 1 = \frac{1}{\varphi}$. Now we can substitue it into your sum:
$$\sum_{j = 0}^n \left((-1)^j \binom{n}{j}F_{j}\right)\\
= \frac{1}{\sqrt5}\sum_{j = 0}^n \left((-1)^j \binom{n}{j} (\varphi^{j} - (-\varphi)^{-j})\right)\\
= \frac{1}{\sqrt5}\left((1 - \varphi)^n - \left(1 + \frac{1}{\varphi}\right)^n\right)\\
= \frac{1}{\sqrt5}\left((-\varphi)^{-n} - \varphi^{n}\right) \\
= -F_{n}.$$
A: Hint: I have been looking for a nice approach by induction for some time but regrettably didn't succeed. Nevertheless since when using exponential generating functions the identity
\begin{align*}
\color{blue}{\sum_{j=0}^n \binom{n}{j}(-1)^j F_j = -F_n}\tag{1}
\end{align*}
becomes obvious at a glance, I'd like to add this information.

*

*Letting $\phi=\frac{1+\sqrt{5}}{2}$ and $F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\left(1-\phi\right)^n\right)$ we recall the exponential generating function of the Fibonacci numbers is
\begin{align*}
\sum_{n=0}^\infty F_n\frac{z^n}{n!}=\frac{1}{\sqrt{5}}\left(e^{\phi z}-e^{(1-\phi)z}\right)
\end{align*}


*The binomial coefficient in (1) indicates we have at the left-hand side a coefficient of $z^n$ when multiplying two exponential generating functions.
\begin{align*}
\left(\sum_{k=0}^{\infty}a_k\frac{z^k}{k!}\right)\left(\sum_{l=0}^{\infty}b_l\frac{z^l}{l!}\right)=\sum_{n=0}^\infty \left(\sum_{j=0}^n\binom{n}{j}a_jb_{n-j}\right)\frac{z^n}{n!}
\end{align*}

With these two aspects in mind the identity (1) reads in terms of exponential generating functions as
\begin{align*}
\color{blue}{\frac{1}{\sqrt{5}}\left(e^{-\phi z}-e^{-\left(1-\phi\right)z}\right)e^{z}
=-\frac{1}{\sqrt{5}}\left(e^{\phi z}-e^{\left(1-\phi\right)z}\right)}
\end{align*}
which is obvious.

