Prove that $\sum_{X=0}^N u(X) {N \choose X} p^X (1-p)^{N-X}=0 \iff u(X)=0, \space \forall X\in\{ 0,1,...,N \}$

Question

I am trying to prove that $Bin(N,p)$ where $N$ is fixed is a complete distribution.

Thus my goal is to show

$$E[u(X)]=0 \iff u(X)=0$$

While I was attempting to prove this I have noticed that

$$\sum_{X=0}^N u(X) {N \choose X} p^X (1-p)^{N-X}$$

is a degree-$N$ polynomial congruent to $0$ making all coefficients equal to $0$.

Here, the coefficients ends up being a nice linear combination which I suspect that it is a form of binomial coefficients.

For example, when $N=3$ I get the following

$$\begin{align} \sum_{X=0}^3 u(X) {3 \choose X} p^X (1-p)^{3-X}= \\ & \quad p^3*(u(3)-3u(2)+3u(1)-u(0)) \\ &+p^2*3(u(2)-2u(1)+u(0)) \\ &+p*3(u(1)-u(0)) \\ &+1(u(0))\\ \end{align}$$

$$ = p^3\sum_{i=0}^3u(i){3 \choose i}(-1)^i +p^2\sum_{i=0}^2u(i){2 \choose i}(-1)^i +p\sum_{i=0}^1u(i){1 \choose i}(-1)^i + u(0)$$

$$=\sum_{j=0}^3\sum_{i=0}^j u(i){3 \choose j}{j \choose i}(-1)^ip^j$$

The part that I would like have assistance is to show that

$$\sum_{X=0}^N u(X) {N \choose X} p^X (1-p)^{N-X}=\sum_{j=0}^N\sum_{i=0}^j u(i){N \choose j}{j \choose i}(-1)^ip^j$$

and that the cascades of $u(i)=0$ occurs, i.e., $$u(0)=0 \implies u(1)=0 \implies ... \implies u(N)=0$$

I appreciate your assistance.

Answer 1

This is an answer that summarizes the question and the comments.

The goal is to show that

$$E[u(X)]=0 \iff u(X)=0$$

and the given equation is equivalent to

$$\sum_{X=0}^n u(X) {N \choose X} p^X (1-p)^{N-X} = \sum_{j=0}^N \sum_{i=0}^j u(i){N \choose j} {j \choose i}(-1)^ip^j = 0$$

We are assuming that $N$ is fixed and $p \in [0,1]$

The middle column is a Bernstein Polynomial that is a base, thus if it is equal to $0$ then $u(X)=0$.

This shows that $Bin(N,p)$ is a complete distribution.

Answer 2

What you can do is differentiate with respect to $p$.

If you assume that:

$$\forall p \in [0,1] \: \sum_{X=0}^N u(X) \binom N X p^X (1-p)^{N-X} $$

then you certainly have for $p=0$ that $u(0)=0$. So your first term disappears.

When you differentiate once, only the term $X=1$ where you differentiate $p^1$ once remains (you don't need to differentiate the $(1-p)^{N-1}$ because it's multiplied by $p^1$ which will give $0$ when you take $p=0$). So $u(1)=0$ and the second term disappears, and so on and so forth.

What you need to prove to make it work is that: $$\frac{d^X}{dp^X}\left[p^X(1-p)^{N-X}\right]|_{p=0}=X!$$ and for all $Y>X$: $$\frac{d^X}{dp^X}\left[p^Y(1-p)^{N-Y}\right]|_{p=0}=0$$

You can use Leibniz formula for a clean proof.

Answer 3

Here's an elementary proof.

$\begin{array}\\ s(n, p) &=\sum_{k=0}^n u(k) {n \choose k} p^k (1-p)^{n-k}\\ &=\sum_{k=0}^n u(n-k) {n \choose n-k} p^{n-k} (1-p)^{k}\\ &=\sum_{k=0}^n \sum_{j=0}^{k}u(n-k) {n \choose k} p^{n-j} \binom{k}{j}(-1)^{k-j}\\ &=\sum_{j=0}^n \sum_{k=j}^{n}u(n-k) {n \choose k} p^{n-j} \binom{k}{j}(-1)^{k-j}\\ &=\sum_{j=0}^n p^j\sum_{k=n-j}^{n}u(n-k) {n \choose k} \binom{k}{n-j}(-1)^{k-n+j}\\ &=\sum_{j=0}^n p^j(-1)^{n-j}\sum_{k=n-j}^{n}u(n-k) \dfrac{n!k!}{k!(n-k)!(n-j)!(k-n+j)!}(-1)^{k}\\ &=\sum_{j=0}^n p^j(-1)^{j}\dfrac{n!}{(n-j)!}\sum_{k=n-j}^{n}u(n-k)(-1)^{n-k} \dfrac{1}{(n-k)!(k-n+j)!}\\ &=\sum_{j=0}^n p^j(-1)^{j}\dfrac{n!}{(n-j)!}\sum_{k=0}^{j}u(k)(-1)^{k} \dfrac{1}{(k)!(j-k)!}\\ &=\sum_{j=0}^n p^j(-1)^{j}\dfrac{n!}{j!(n-j)!}\sum_{k=0}^{j}u(k)(-1)^{k} \dfrac{j!}{(k)!(j-k)!}\\ &=\sum_{j=0}^n p^j(-1)^{j}\binom{n}{j}\sum_{k=0}^{j}u(k)(-1)^{k}\binom{j}{k}\\ \end{array} $

If $s(n, p) = 0$ for all $p$, then, since it is a polynomial in $p$, all its coefficients must be zero. Therefore $\sum_{k=0}^{j}u(k)(-1)^{k}\binom{j}{k} = 0 $ for all $j$. Starting with $j=0$, this shows that $u(k) = 0$ for all $k$.