Kravchuk polynomials

For any prime power q and positive integer n, define the Kravchuk polynomial $${\displaystyle {\begin{aligned}{\mathcal {K}}_{k}(x;n,q)={\mathcal {K}}_{k}(x)={}&\sum _{j=0}^{k}(-1)^{j}(q-1)^{k-j}{\binom {x}{j}}{\binom {n-x}{k-j}}\\={}&\sum _{j=0}^{k}(-1)^{j}(q-1)^{k-j}{\frac {x^{\underline {j}}}{j!}}{\frac {(n-x)^{\underline {k-j}}}{(k-j)!}}\end{aligned}}}$$ for ${\displaystyle k=0,1,\ldots ,n}$. In the second line, the factors depending on ${\displaystyle x}$ have been rewritten in terms of falling factorials, to aid readers uncomfortable with non-integer arguments of binomial coefficients.

The Kravchuk polynomial has the following alternative expressions:

${\displaystyle {\mathcal {K}}_{k}(x;n,q)=\sum _{j=0}^{k}(-q)^{j}(q-1)^{k-j}{\binom {n-j}{k-j}}{\binom {x}{j}}.}$

${\displaystyle {\mathcal {K}}_{k}(x;n,q)=\sum _{j=0}^{k}(-1)^{j}q^{k-j}{\binom {n-k+j}{j}}{\binom {n-x}{k-j}}.}$

Note that there is more that merely recombination of material from the two binomial coefficients separating these from the above definition. In these formulae, only one term of the sum has degree ${\displaystyle k}$, whereas in the definition all terms have degree ${\displaystyle k}$.

For integers ${\displaystyle i,k\geq 0}$, we have that

${\displaystyle {\begin{aligned}(q-1)^{i}{n \choose i}{\mathcal {K}}_{k}(i;n,q)=(q-1)^{k}{n \choose k}{\mathcal {K}}_{i}(k;n,q).\end{aligned}}}$

For non-negative integers r, s,

${\displaystyle \sum _{i=0}^{n}{\binom {n}{i}}(q-1)^{i}{\mathcal {K}}_{r}(i;n,q){\mathcal {K}}_{s}(i;n,q)=q^{n}(q-1)^{r}{\binom {n}{r}}\delta _{r,s}.}$

The generating series of Kravchuk polynomials is given as below. Here ${\displaystyle z}$ is a formal variable.

${\displaystyle {\begin{aligned}(1+(q-1)z)^{n-x}(1-z)^{x}&=\sum _{k=0}^{\infty }{\mathcal {K}}_{k}(x;n,q){z^{k}}.\end{aligned}}}$

The Kravchuk polynomials satisfy the three-term recurrence relation

${\displaystyle {\begin{aligned}x{\mathcal {K}}_{k}(x;n,q)=-q(n-k){\mathcal {K}}_{k+1}(x;n,q)+(q(n-k)+k(1-q)){\mathcal {K}}_{k}(x;n,q)-k(1-q){\mathcal {K}}_{k-1}(x;n,q).\end{aligned}}}$

• Krawtchouk matrix
• Hermite polynomials