I recently read an article where they used the Kravchuk polynomials:
$$P_{j}(x ; n)=\sum_{i=0}^{j}(-1)^{i}\left(\begin{array}{l} x \\ i \end{array}\right)\left(\begin{array}{c} n-x \\ j-i \end{array}\right)\text{,}$$ which are discrete orthogonal polynomials associated with the binomial distribution. However, they mention that the polynomials can be easily calculated using the following recursive formula:
- $P_{0}(x ; n)=1$
- $P_{j}(0 ; n)= \left(\begin{array}{l} n \\ j \end{array}\right)$
- $P_{j}(x ; n)=P_{j}(x-1 ; n) - P_{j-1}(x ; n) -P_{j-1}(x-1 ; n)$
I cannot figure out how they obtained this recursive formula, and the article provides no reference so I'm asking for help.
Also, they compute this polynomial for values of $j$ and $x$ both ranging from $0$ to $n$. And I'm wondering what happens to the binomial coefficient $\left(\begin{array}{l} x \\ i \end{array}\right)$, when $j>x$ and that some values of $i$ are also larger than $x$.
When $k>n$, the usual convention is that $\binom{n}{k}=0$ -- which matches the combinatorial viewpoint that there is no way to choose $k$ elements in a set of $n$ elements.
As for the recurrence formula, it can be deduced from successive applications of Pascal's identity:
$$\begin{align*} P_j(x,n)+P_{j-1}(x,n)&=\sum_{i=0}^{j-1} (-1)^i \left(\binom{x}{i} \binom{n-x}{j-i}+\binom{x}{i} \binom{n-x}{j-i-1}\right)+(-1)^j\binom{x}{j}\\ &=\sum_{i=0}^{j-1} (-1)^i \binom{x}{i} \binom{n-x+1}{j-i}+(-1)^j\binom{x}{j}\\ &=\sum_{i=0}^{j} (-1)^i \binom{x}{i} \binom{n-x+1}{j-i}\\ &=\sum_{i=0}^{j} (-1)^i \binom{x-1}{i} \binom{n-x+1}{j-i}+\sum_{i=1}^{j} (-1)^i\binom{x-1}{i-1} \binom{n-x+1}{j-i}\\ &=\sum_{i=0}^{j} (-1)^i \binom{x-1}{i} \binom{n-x+1}{j-i}-\sum_{i=0}^{j-1} (-1)^i\binom{x-1}{i} \binom{n-x+1}{j-i-1}\\ &= P_j(x-1,n)-P_{j-1}(x-1,n). \end{align*}$$