From Binet’s formula we have
$\sqrt{5}F_n=\phi^n-(-\phi)^{-n}$
and since $\phi^2 = \left(\frac{1+\sqrt5}{2}\right)^2 = \frac{1+2\sqrt5+5}{4} > \frac{10}{4} > 2$ we have
$\sqrt{5}F_n + \frac12 > \phi^n \space \forall n\ge 2$
But $\sqrt{5}F_n$ cannot be as great as $\phi^{n+1}$ so
$n<\log_{\phi}(\sqrt{5}F_n+\frac12)<n+1 \space \forall n \ge2$
In seeking to evaluate
$${q-j+k\choose k}
- \sum_{\ell=0}^{\lfloor k/2 \rfloor}
{q/2+\ell\choose 2\ell}
\left({q/2-j+k-\ell\choose k-2\ell}
+ {q/2-j+k-\ell-1\choose k-2\ell} \right)$$
We get for the first piece of the sum
$$\sum_{\ell=0}^{\lfloor k/2 \rfloor}
{q/2+\ell\choose 2\ell} {q/2-j+k-\ell\choose k-2\ell}
\\ = \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{1}{z^{k+1}}
(1+z)^{q/2-j+k}
\sum_{\ell=0}^{\lfloor k/2 \rfloor}
{q/2+\ell\choose 2\ell} \frac{z^{2\ell}}{(1+z)^\ell}
\; dz.$$
Now here the residue vanishes when $2\ell \gt k$ so it enforces the
upper limit of the sum and we obtain
$$\frac{1}{2\pi i} \int_{|z|=\varepsilon}
\frac{(1+z)^{q/2-j+k}}{z^{k+1}}
\\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{q/2}}{w}
\sum_{\ell\ge 0}
\frac{z^{2\ell}}{(1+z)^\ell} \frac{(1+w)^\ell}{w^{2\ell}}
\; dw \; dz
\\ = \frac{1}{2\pi i} \int_{|z|=\varepsilon}
\frac{(1+z)^{q/2-j+k}}{z^{k+1}}
\\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{q/2}}{w}
\frac{1}{1-z^2(1+w)/(1+z)/w^2}
\; dw \; dz
\\ = \frac{1}{2\pi i} \int_{|z|=\varepsilon}
\frac{(1+z)^{q/2-j+k+1}}{z^{k+1}}
\\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} (1+w)^{q/2}
\frac{w}{(w-z)(w(1+z)+z)}
\; dw \; dz.$$
The pole at $w=0$ has been canceled. Now observe that for the geometric
series to converge we must have $$|z^2(1+w)/w^2/(1+z)|\lt 1.$$ We will
choose a contour that includes both simple poles. The first pole is at
$-z/(1+z).$ We thus require $|z/(1+z)| \lt \gamma.$ With $|z/(1+z)| \le
\varepsilon/(1-\varepsilon)$ we get $\varepsilon/(1-\varepsilon) \lt
\gamma$ and we furthermore need $|z^2/(1+z)| \lt |w^2/(1+w)|.$ The latter
holds if $\varepsilon^2 / (1-\varepsilon) \lt \gamma^2/(1+\gamma).$ Both
hold if $\varepsilon \gamma \lt \gamma^2/(1+\gamma)$ or $\varepsilon \lt
\gamma/(1+\gamma).$ So $\varepsilon = \gamma^2/(1+\gamma)$ will work.
Observe that this contour also includes the pole at $w=z.$
First pole. Now to extract the residue at $w=-z/(1+z)$ we write
$$\frac{1}{2\pi i} \int_{|z|=\varepsilon}
\frac{(1+z)^{q/2-j+k}}{z^{k+1}}
\\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} (1+w)^{q/2}
\frac{w}{(w-z)(w+z/(1+z))}
\; dw \; dz$$
and obtain
$$\frac{1}{2\pi i} \int_{|z|=\varepsilon}
\frac{(1+z)^{q/2-j+k}}{z^{k+1}}
(1+z)^{-q/2} \frac{-z/(1+z)}{-z/(1+z)-z} \; dz
\\ = \frac{1}{2\pi i} \int_{|z|=\varepsilon}
\frac{(1+z)^{k-j}}{z^{k+1}} \frac{1}{z+2} \; dz.$$
Repeating for the second sum we get
$$\frac{1}{2\pi i} \int_{|z|=\varepsilon}
\frac{(1+z)^{k-j-1}}{z^{k+1}} \frac{1}{z+2} \; dz.$$
Adding the two we find
$$\frac{1}{2\pi i} \int_{|z|=\varepsilon}
\frac{(1+z)^{k-j-1} (1+(1+z))}{z^{k+1}} \frac{1}{z+2} \; dz
= {k-j-1\choose k}.$$
Second pole. For the residue at $w=z$ we obtain for the first
sum
$$\frac{1}{2\pi i} \int_{|z|=\varepsilon}
\frac{(1+z)^{q/2-j+k+1}}{z^{k+1}}
(1+z)^{q/2}
\frac{z}{(z(1+z)+z)}
\; dz
\\ = \frac{1}{2\pi i} \int_{|z|=\varepsilon}
\frac{(1+z)^{q-j+k+1}}{z^{k+1}}
\frac{1}{z+2}
\; dz.$$
Repeating for the second sum we get
$$\frac{1}{2\pi i} \int_{|z|=\varepsilon}
\frac{(1+z)^{q-j+k}}{z^{k+1}}
\frac{1}{z+2}
\; dz.$$
Adding the two we find
$$\frac{1}{2\pi i} \int_{|z|=\varepsilon}
\frac{(1+z)^{q-j+k}(1+(1+z))}{z^{k+1}}
\frac{1}{z+2}
\; dz = {q-j+k\choose k}.$$
Conclusion. Collecting everything we obtain
$${q-j+k\choose k} - {q-j+k\choose k}
- {k-j-1\choose k}.$$
This is $- (k-j-1)^{\underline{k}}/k!.$ Now if $0\le j\lt k$ this is
indeed zero because the falling factorial hits the zero value. If $j\ge
k$ all $k$ terms are negative and we get $-(-j)^{\overline{k}}/k!.$
We have at last
$$\bbox[5px,border:2px solid #00A000]{
(-1)^{k+1} {j\choose k}.}$$
as claimed.
Remark. The potential square roots that appeared in the above all
use the principal branch of the logarithm with branch cut $(-\infty,
-1]$ which means everything is analytic in a neighborhood of zero as
required.
Best Answer
Easy algebraic proof. Just use Binet's formula: $$F_n = \frac{1}{\sqrt{5}} \left( \left(\frac{1 + \sqrt{5}}{2} \right)^n - \left(\frac{1 - \sqrt{5}}{2} \right)^n \right) $$ If you expand the powers using binomial coefficients and simplify, you will see that terms with $\sqrt{5}$ cancel and you should get your desired result exactly!