Recurrence relation for Kravchuk polynomials I'm reading this article, where they use the following equivalent expressions for the Kravchuk polynomials: \begin{equation}
    \begin{split}
        K_j(i) &= \sum_{h=0}^j (-1)^h(q-1)^{j-h} \binom{i}{h}\binom{d-i}{j-h} \\
        &= \sum_{h=0}^j (-q)^h(q-1)^{j-h} \binom{i}{h}\binom{d-h}{j-h} \\
        &= \sum_{h=0}^j (-1)^h q^{j-h} \binom{d-i}{j-h}\binom{d-j+h}{h}
    \end{split}
\end{equation}
In the paper, they claim that the following recurrence relation holds for $i,j\geq 1$ without any proof: \begin{equation}
    (q-1)(d-i)K_j(i+1) - (i+(q-1)(d-i)-qj)K_j(i) + i K_j(i-1) = 0
\end{equation}
Could anyone help me figuring out how to prove this?
 A: Here is a direct, human and constructive proof (no need to know in advance what has to be proven):
Let $[x^h]f(x)$ be the coefficient of $x^h$ in the formal power series expansion of $f(x)$.  We have
$$ {i\choose h} = [x^h](1+x)^i$$ and
$$ {d-i\choose j- h} = [x^{j-h}](1+x)^{d-i}$$ then
$$  K_j(i,d)=\sum_{h=0}^j (-1)^h[x^h](1+x)^i(q-1)^{j-h} [x^{j-h}](1+x)^{d-i}$$
$$  K_j(i,d)=\sum_{h=0}^j [x^h](1-x)^i [x^{j-h}](1+(q-1)x)^{d-i}$$
$$  K_j(i,d)=[x^j](1-x)^i (1+(q-1)x)^{d-i}.$$
Let $f_{i,d}(x):= (1-x)^i (1+(q-1)x)^{d-i}$.
$$ f_{i,d}'(x)= -i(1-x)^{i-1}(1+(q-1)x)^{d-i}+(1-x)^i (d-i)(q-1)(1+(q-1)x)^{d-i-1}$$
$$ f_{i,d}'(x)=-if_{i-1,d-1}(x)+(d-i)(q-1)f_{i,d-1}(x)$$
$$ f_{i,d+1}'(x)=-if_{i-1,d}(x)+(d+1-i)(q-1)f_{i,d}(x).$$ Then
$$[x^j]f_{i,d+1}'(x)=-iK_j(i-1,d)+(d+1-i)(q-1)K_j(i,d) $$
$$(j+1)[x^{j+1}]f_{i,d+1}(x)=-iK_j(i-1,d)+(d+1-i)(q-1)K_j(i,d) $$
$$\color{red}{(j+1)K_{j+1}(i,d+1)=-iK_j(i-1,d)+(d+1-i)(q-1)K_j(i,d)}. $$
Now $$K_j(i,d+1)=[x^j](1-x)^i (1+(q-1)x)^{d-i}(1+(q-1)x)$$
$$K_j(i+1,d+1)=[x^j](1-x)^{i+1} (1+(q-1)x)^{d-i}$$
$$K_j(i+1,d+1)=[x^j](1-x)^{i} (1+(q-1)x)^{d-i}-[x^{j-1}](1-x)^{i} (1+(q-1)x)^{d-i}, $$
that is:
$$K_j(i,d+1)=K_j(i,d)+ (q-1)K_{j-1}(i,d)$$
$$K_j(i+1,d+1)=K_j(i,d)-K_{j-1}(i,d), $$
this gives :
$$\color{Blue}{K_j(i,d)-K_j(i+1,d)=qK_{j-1}(i,d-1)}.$$
Starting from the red equation, shifting the index $j$, and $d+1$ for $d$, multiplying by $q$ and making use of the blue equation, the desired recursion is eventually obtained:
$$(j+1)K_{j+1}(i,d+1) =(q-1)(d+1-i)K_{j}(i,d)-iK_{j}(i-1,d)  $$
$$-(q-1)(d-i)K_{j-1}(i,d-1)+iK_{j-1}(i-1,d-1) +jK_j(i,d) = 0$$
$$-q(q-1)(d-i)K_{j-1}(i,d-1)+qiK_{j-1}(i-1,d-1) +qjK_j(i,d) = 0$$
$$ (q-1)(d-i)(K_j(i+1,d)-K_j(i,d)) +qiK_{j-1}(i-1,d-1) +qjK_j(i,d) = 0$$
$$ (q-1)(d-i)(K_j(i+1,d)-K_j(i,d)) -i(K_j(i,d)-K_j(i-1,d)) +qjK_j(i,d) = 0$$
$$ (q-1)(d-i)(K_j(i+1,d)-K_j(i,d)) - (i-qj)K_j(i,d) + i K_j(i-1,d) = 0$$
$$ (q-1)(d-i)K_j(i+1,d) - (i+(q-1)(d-i)-qj)K_j(i,d) + i K_j(i-1,d) = 0.$$
A: Commentary: The following is a proof of the identity in their paper, and also a justification of why no proof needed to be given. Using the methods of the book A = B, this entire proof is derived using a general algorithm that requires no cleverness to execute, meaning their identity can be proved by a computer.

Recurrences for sums like this can be derived automatically using Zeilberger's algorithm. I used the CAS Maxima to do this, as follows:
load(zeilberger)$
Zeilberger((-1)^h * (q - 1)^(j - h) * binomial(i, h) * binomial(d - i, j - h), h, i);

Output:  $[[\frac{h(i+1)(j−d−1)(j+i−h−d)(q−1)}{(i−d)(i−h+1)(i−h+2)},[\color{blue}{i+1},\color{#080}{jq+iq−dq+q−2i+d−2},\color{purple}{−(i−d+1)(q−1)}]]]$
Here's how we interpret this output. Let $F(h,i)=(-1)^h (q-1)^{j-h} \binom{i}h\binom{d-i}{j-h}$ be the summation term. Let
$$
\begin{align}
R(h,i)&=\frac{h(i+1)(j−d−1)(j+i−h−d)(q−1)}{(i−d)(i−h+1)(i−h+2)}
\\a_0&=\color{blue}{i+1}
\\a_1&=\color{#080}{jq+iq−dq+q−2i+d−2}
\\a_2&=\color{purple}{−(i−d+1)(q−1)}
\end{align}
$$ denote the various elements of the output, and let
$$
G(h,i)=R(h,i)F(h,i)
$$
You can show, through tedious algebraic manipulations alone involving canceling a lot of common factorials, that
$$
\begin{align}
\forall h,i\ge 0: 
\quad &G(h+1,i)-G(h,i)=a_0 F(h,i)+a_1F(h,i+1)+a_2 F(h,i+2)\tag{$*$}
\end{align}
$$
Now, take the above equation, and sum over all $h\in \{0,1,2,\dots\}$. The left hand side is a telescoping sum since $G(h,i)$ is nonzero for only finitely many $h$, so the LHS sums to $-G(0,i)=0$. The RHS, on the other hand obviously sums to $a_0 K_j(i)+a_1 K_j(i+1)+a_2 K_j(i+2)$, so we conclude
$$
0=a_0 K_j(i)+a_1 K_j(i+1)+a_2 K_j(i+2)
$$
This is equivalent to your identity, after some much easier algebraic manipulations.
By the way, this Mathematica code serves as a proof of $(*)$. When you run it, the output is 0.
F[h_, i_] := (-1)^h (q - 1)^(j - h) Binomial[i, h] Binomial[d - i, j - h]
R[h_, i_] := 
 h (i + 1) (j - d - 1) (j + i - h - d) (q - 1)/((i - d) (i - h + 1) (i - h + 2))
G[h_, i_] := F[h, i]*R[h, i]
a0 = i + 1;
a1 = j q + i q - d q + q - 2 i + d - 2;
a2 = -(i - d + 1) (q - 1);

LHS = G[h + 1, i] - G[h, i];
RHS = a0 F[h, i] + a1 F[h, i + 1] + a2 F[h, i + 2];
FunctionExpand[LHS - RHS]

