Basic Proof of Properties of Kravchuk Polynomials Fix $n$ and consider the family of polynomials
$$
K_s(\ell) = \sum_{k=0}^s(-1)^k\binom{\ell}{k}\binom{n-\ell}{s-k} \quad \text{defined for} \quad 0 \leq s \leq n
$$
They are called Kravchuk (or Krawtchouk) polynomials.
They are used in a paper I am trying to understand.
The key properties of the polynomials that are used are that if you define the inner product
$$
\langle f, g \rangle = \mathbf{E}_{k \leftarrow Bin(n,\frac{1}{2})}\big[f(k)g(k)\big]
$$
where $Bin(n,\frac{1}{2})$ is the binomial distribution,
on the vector space of functions $\mathbb R^{\{0,1,\ldots,n\}}$ then
$$
\langle K_s, K_r\rangle = \begin{cases} \binom{n}{s} & r=s\\ 0 & r \neq s\end{cases}
$$
so that they form an orthogonal basis, and
$$
\binom{n}{r}K_s(r) = \binom{n}{s}K_r(s)
$$
which allows some computations to be simplified.
However, there seem to be no simple proofs of these facts anywhere; any proof I have found proves this as a special case of some much more general theory and it is too complicated for me to understand.
Can someone give a basic proof of these identities?
 A: First, we give a probabilistic interpretation of $K_s(\ell)$.
Let $A$ be a fixed subset of $\{1,\dots,n\}$ with size $\ell$.
Let $B$ be a randomly chosen subset of $\{1,\dots,n\}$, uniformly chosen from subsets of size $s$.
Then
$$
K_s(\ell)=\binom{n}s \mathbb E\left[(-1)^{|A\cap B|}\right]\tag{1}
$$
This follows by computing $E\left[(-1)^{|A\cap B|}\right]$. A similar computation proves that
$$
\langle K_s,K_r\rangle
=\binom{n}s\binom{n}r\mathbb E\left[(-1)^{|A\cap B|}(-1)^{|A\cap C|}\right],\tag{2}
$$
where

*

*$A$ is randomly chosen from all subsets of $\{1,\dots,n\}$,

*$B$ is randomly chosen from all subsets of $\{1,\dots,n\}$ of size $s$, and

*$C$ is randomly chosen from all subsets of $\{1,\dots,n\}$ of size $r$,

all independently of each other. Now, imagine you first choosen $B$ and $C$ randomly, and then choose $A$. There are two things that can happen:

*

*$B$ and $C$ are different sets. In this case, it is not hard to show the conditional expectation of $E\left[(-1)^{|A\cap B|}(-1)^{|A\cap C|}\right]$ given $B$ and $C$ is zero. Indeed, choosing any element $x$ of the symmetric difference $B\Delta C$, then flipping whether or not $x\in A$ will flip the sign of $E\left[(-1)^{|A\cap B|}(-1)^{|A\cap C|}\right]$.


*$B$ and $C$ are the same set, which is only possible when $r=s$. This happens with probability $1/\binom{n}s$, and in these cases, $E\left[(-1)^{|A\cap B|}(-1)^{|A\cap C|}\right]=1$ surely.
The preceding two bullets, combined with $(2)$, imply that $\langle K_s,K_r\rangle$ is zero when $r\neq s$, and $\binom{n}s$ when they are equal.
The same interpretation proves $$\frac{K_s(r)}{\binom{n}{s}}=\frac{K_r(s)}{\binom{n}r}$$
Both sides are equal to $\mathbb E\left[(-1)^{|A\cap B|}\right]$, where $|A|=r$ and $|B|=s$. The only difference is whether $A$ is fixed and $B$ is random, or the other way  around, but this makes no difference to the expectation.
