# Recurrence relation for Kravchuk polynomials

I'm reading this article, where they use the following equivalent expressions for the Kravchuk polynomials: $$$$\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}$$$$ In the paper, they claim that the following recurrence relation holds for $$i,j\geq 1$$ without any proof: $$$$(q-1)(d-i)K_j(i+1) - (i+(q-1)(d-i)-qj)K_j(i) + i K_j(i-1) = 0$$$$ Could anyone help me figuring out how to prove this?

• If I am not mistaken, $K_j(i,d)$ is the coefficient of $x^j$ in the polynomial $(1-x)^i (1+(q-1)x)^{d-i}$ of degree $d$. That might be starting point. Commented Dec 1, 2021 at 21:18
• @RenéGy I hadn't looked at it that way, but it doesn't help me any further yet. How can I use this fact in the proof? Commented Dec 2, 2021 at 13:00
• I would let $f_{i,d}(x):= (1-x)^i (1+(q-1)x)^{d-i}$ and then write the coefficient of $x^j$ in the derivative of $f_{i,d}(x)$ in two ways: (i) as $(j+1) K_{j+1}(i,d)$ and (ii) as $-iK_j(i-1,d-1)+(d-i)(q-1)K_j(i,d-1)$. Not sure if it readily works though ... Commented Dec 2, 2021 at 17:09
• @RenéGy I tried a bunch of things using this idea, but it didn't get me anywhere, so I don't think this works. Thanks for the suggestion though! Commented Dec 3, 2021 at 11:03

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.$$

• Impressive! ${}{}$ Commented Dec 5, 2021 at 18:20

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]

• Thanks for the answer! I'm still hoping for an algebraic way to prove this, but this is sufficient for now. Commented Dec 3, 2021 at 11:05