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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – René Gy
    Dec 1, 2021 at 21:18
  • $\begingroup$ @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? $\endgroup$ Dec 2, 2021 at 13:00
  • $\begingroup$ 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 ... $\endgroup$
    – René Gy
    Dec 2, 2021 at 17:09
  • $\begingroup$ @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! $\endgroup$ Dec 3, 2021 at 11:03

2 Answers 2


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

  • $\begingroup$ Impressive! ${}{}$ $\endgroup$ 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:

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]
  • $\begingroup$ Thanks for the answer! I'm still hoping for an algebraic way to prove this, but this is sufficient for now. $\endgroup$ Dec 3, 2021 at 11:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .