Derivation of Kravchuk polynomial identity I am working my way through N.J.A. Sloane "An Introduction to Association Schemes and Coding Theory" and have got stuck proving the last of his identities for the Kravchuck (Krawtchouk) polynomials.  The Kravchuk polynomial is defined as
$$
K_k(i;n) = \sum_{j=0}^k (-1)^j \binom{i}{j} \binom{n-i}{k-j}
$$
I know (have proved) the following equivalent formulations
$$
K_k(i;n) = \sum_{j=0}^k (-2)^j \binom{i}{j} \binom{n-j}{k-j} \\
=  \sum_{j=0}^k (-1)^j 2^{k-j} \binom{n-k+j}{j} \binom{n-i}{k-j}\\
$$
I know that if $u \in \mathbb{F}_2^n$ has weight, $wt(u)=i$ then
$$
K_{k}(i;n) = \sum_{v \in \mathbb{F}_2^n \\ wt(v) = k} (-1)^{u \cdot v}
$$
I know that $K_k(i;n)$ is the coefficient of $z^k$ in $(1+z)^{n-i}(1-z)^{i}$.  I know the orthogonality conditions:
$$
\sum_{i=0}^{n} \binom{n}{i} K_k(i;n) K_l(i;n) = 2^n\binom{n}{k} \delta_{k,l}
$$
I have also proved the following properties
$$
\binom{n}{i} K_k(i;n) = \binom{n}{k} K_{i}(k;n) \\
(k+1)K_{k+1}(i;n) = (n-2i)K_k(i;n) - (n-k+1)K_{k-1}(i;n) \\
\sum_{j=0}^k K_j(i;n) = K_k(i-1;n-1)
$$
But I am really stuck on proving this one
$$
\sum_{\ell =0}^n \binom{n-\ell}{n-j} K_{\ell}(i;n) = 2^j \binom{n-i}{j}
$$
 A: Defining the Kravchuck polynomial as (the definition in its full
generality is at
Wikipedia)
$$\mathcal{K}_k(x;n) =
\sum_{j=0}^k (-1)^j {x\choose j} {n-x\choose k-j}$$
we seek to show that
$$\sum_{\ell=0}^n {n-\ell\choose n-m} \mathcal{K}_\ell(x; n)
= 2^m \times {n-x\choose m}.$$
We prove this for $x=p$ an integer and then it holds for all $x$
because $\mathcal{K}_k(x;n)$ is a polynomial in $x.$
We have
$$\mathcal{K}_k(p; n) = [z^k] (1+z)^{n-p}
\sum_{j=0}^k (-1)^j {p\choose j} z^j.$$
Here the coefficient extractor enforces the upper limit of the sum and
we get
$$\mathcal{K}_k(p; n) = [z^k] (1+z)^{n-p}
\sum_{j\ge 0} (-1)^j {p\choose j} z^j
= [z^k] (1+z)^{n-p} (1-z)^p.$$
We also get for the coveted identity that it is
$$\sum_{\ell=0}^n {\ell\choose n-m} \mathcal{K}_{n-\ell}(p; n)
= \sum_{\ell=0}^n {\ell\choose n-m}
[z^{n-\ell}] (1+z)^{n-p} (1-z)^p
\\ = [z^n] (1+z)^{n-p} (1-z)^p
\sum_{\ell=0}^n {\ell\choose n-m}
z^\ell
\\ = [z^n] (1+z)^{n-p} (1-z)^p
\sum_{\ell=n-m}^n {\ell\choose n-m}
z^\ell
\\ = [z^m]  (1+z)^{n-p} (1-z)^p
\sum_{\ell=0}^m {\ell+n-m\choose n-m}
z^\ell.$$
Now here we have another coefficient extractor enforcing the upper
range of the sum and we get
$$[z^m]  (1+z)^{n-p} (1-z)^p
\sum_{\ell\ge 0} {\ell+n-m\choose n-m}
z^\ell
\\ = [z^m] (1+z)^{n-p} (1-z)^p \frac{1}{(1-z)^{n-m+1}}.$$
This is
$$\frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{1}{z^{m+1}}
(1+z)^{n-p} (1-z)^{m-1} \frac{1}{(1-z)^{n-p}} \; dz.$$
Now put $(1+z)/(1-z) = w$ so that $z = (w-1)/(1+w)$ and $dz = 2/(1+w)^2
\; dw$ to obtain (observe that due to the fact that $w=1+2z+\cdots$ the
image of a small circle  $|z|=\varepsilon$ can be deformed to another
small circle $|w-1|=\gamma$  because when $z$ makes one turn around zero
so does $w$ around one)
$$\frac{1}{2\pi i} \int_{|w-1|=\gamma}
\frac{(1+w)^{m+1}}{(w-1)^{m+1}}
w^{n-p} \frac{2^{m-1}}{(1+w)^{m-1}}
\frac{2}{(1+w)^2} \; dw
\\ = \frac{2^m}{2\pi i} \int_{|w-1|=\gamma}
\frac{1}{(w-1)^{m+1}} w^{n-p} \; dw
\\ = \frac{2^m}{2\pi i} \int_{|w-1|=\gamma} \frac{1}{(w-1)^{m+1}}
\sum_{r\ge 0} {n-p\choose r} (w-1)^r \; dw.$$
There were no poles other than $w=1$ inside the image contour and the
series in $w-1$ converges including for $n-p \lt 0$ because $\gamma\ll 1.$
This yields
$$\bbox[5px,border:2px solid #00A000]{
2^m \times {n-p\choose m}}$$
as claimed.
A: Here is another proof I worked out for the case that $0 \leq i \leq n$ is an integer.  It uses the binomial expansion
$$
(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}
$$
in two places and the fact that when $i$ is an integer in the given range
$$
\sum_{k=0}^{n} K_k(i;n) y^k = (1+y)^{n-i}(1-y)^{i}.
$$
We want to show that
$$
-2^j\binom{n-i}{j} + \sum_{\ell=0}^{n} \binom{n-\ell}{n-j} K_{\ell}(i;n) = 0
$$
for all $0 \leq j \leq n$. We form the generating function whose coefficient of $z^j$ is the left hand side of the desired identity:
$$
F(z) = \sum_{j=0}^{n} \left(-2^j\binom{n-i}{j} + \sum_{\ell=0}^{n} \binom{n-\ell}{n-j} K_{\ell}(i;n)\right) z^j \\
 = \sum_{j=0}^n -(2z)^j \binom{n-i}{j} + \sum_{j=0}^n \sum_{\ell=0}^{n} \binom{n-\ell}{n-j}K_{\ell}(i;n) z^j \\
= -(1+2z)^{n-i} + \sum_{j=0}^n \sum_{\ell=0}^{n} \binom{n-\ell}{n-j}K_{\ell}(i;n) z^j \\
= -(1+2z)^{n-i} + \sum_{\ell=0}^{n} \sum_{j=0}^n \binom{n-\ell}{n-j}K_{\ell}(i;n) z^j \\
= -(1+2z)^{n-i} + \sum_{\ell=0}^{n} K_{\ell}(i;n) \sum_{j=0}^n \binom{n-\ell}{n-j} z^j \\
= -(1+2z)^{n-i} + \sum_{\ell=0}^{n} K_{\ell}(i;n) z^{\ell} \sum_{j=0}^n \binom{n-\ell}{n-j} z^{j-\ell} \\
= -(1+2z)^{n-i} + \sum_{\ell=0}^{n} K_{\ell}(i;n) z^{\ell} (1+z)^{n-\ell} \\
= -(1+2z)^{n-i} + (1+z)^n \sum_{\ell=0}^{n} K_{\ell}(i;n)\left( \frac{z}{1+z}\right)^{\ell}.
$$
Letting $y = z/(1+z)$, we get
$$
F(z) = -(1+2z)^{n-i} + (1+z)^n \left(1+z/(1+z) \right)^{n-i} \left(1-z/(1+z) \right)^{i} \\
 = -(1+2z)^{n-i} + (1+z)^n (1+2z)^{n-i} (1+z)^{i-n} (1+z)^{-i} \\
 = -(1+2z)^{n-i} + (1+2z)^{n-i} \\
 = 0. \\
$$
Since $F(z) = 0$ the coefficient of $z^j$ in $F(z)$ is $0$ for all $0 \leq j \leq n$.  Going back to the definition of $F(z)$ and extracting the coefficient of $z^j$ gives
$$
-2^j\binom{n-i}{j} + \sum_{\ell=0}^{n} \binom{n-\ell}{n-j} K_{\ell}(i;n) = 0.
$$
as desired.
