# Uniform distribution variable in the Newton symbol

The following question is from actuarial exam. Let $$N$$ be uniformly distributed on $$\{0,1,2,...,19\}$$. Compute $$\mathbb{E}\sum_{k=0}^{N}{N-k \choose k}(-1)^k$$

I started $$\mathbb{E}\sum_{k=0}^{N}{N-k \choose k}(-1)^k=\frac{1}{20}\sum_{n=0}^{19}\mathbb{E}\left(\sum_{k=0}^{N}{N-k \choose k}(-1)^k|N=n\right)=\frac{1}{20}\mathbb{E}\sum_{n=0}^{19}\sum_{k=0}^{n}{n-k \choose k}(-1)^k$$ Here I changed summation variable and the order of summation a couple of times but it didn't work: $$\frac{1}{20}\mathbb{E}\sum_{n=0}^{19}\sum_{k=0}^{n}{n-k \choose k}(-1)^k=\frac{1}{20}\mathbb{E}\sum_{n=0}^{19}\sum_{l=0}^{n}{l \choose n-l}(-1)^{n-l}=\frac{1}{20}\mathbb{E}\sum_{l=0}^{19}\sum_{n=l}^{19}{l \choose n-l}(-1)^{n-l}=\frac{1}{20}\mathbb{E}\sum_{l=0}^{19}\sum_{m=0}^{19-l}{l \choose m}(-1)^{m}$$

The last sum is equal $$0$$ if $$l\leq 9$$. This is because $$\sum_{k=0}^{n}{n \choose k}(-1)^k=0.$$ Hence $$\frac{1}{20}\mathbb{E}\sum_{l=0}^{19}\sum_{m=0}^{19-l}{l \choose m}(-1)^{m}=\frac{1}{20}\mathbb{E}\sum_{l=10}^{19}\sum_{m=0}^{19-l}{l \choose m}(-1)^{m}$$

I also tried to count this sum by setting consecutive $$N=0,1,2,3,4...$$ but I coudn't find any regularity.

We have the sum \begin{align*} \frac1{20}\sum_{n=0}^{19}\sum_{k=0}^n\binom{n-k}k(-1)^k&=\frac1{20}\sum_{k=0}^{19}(-1)^k\sum_{n=k}^{19}\binom{n-k}k\\&=\frac1{20}\sum_{k=0}^{19}(-1)^k\binom{20-k}{k+1}\tag{*}\\&=\frac1{20}\sum_{k=0}^{19}(-1)^k[z^{k+1}](1+z)^{20-k}\tag{**}\\&=\frac1{20}\sum_{k=0}^{\infty}(-1)^k[z^{k+1}](1+z)^{20-k}\\&=\frac1{40\pi i}\sum_{k=0}^{\infty}(-1)^k\int_{|z|=r}\frac{(1+z)^{20-k}}{z^{k+2}}dz\tag{***}\\&=\frac1{40\pi i}\int_{|z|=r}\frac{(1+z)^{20}}{z^2}\frac{1}{1+\frac{1}{z(1+z)}}dz\\&=\frac1{40\pi i}\int_{|z|=r}\frac{(1+z)^{21}}{z(z^2+z+1)}dz\\&=\frac{1}{20}\sum_i \text{res}_{z=z_i}\frac{(1+z)^{21}}{z(z^2+z+1)}. \end{align*} $$(*)$$ : Hockey stick identity is used.
$$(**)$$ : $$[z^n]f(z)$$ denotes the $$n$$-th coefficient $$a_n$$ of $$f(z)=\sum_{i=0}^\infty a_iz^i$$.
$$(***)$$ : $$\int_{|z|=r} z^k dz=2\pi i \mathbf{1}_{k=-1}$$ is used and $$r>1$$ is chosen sufficiently large so that the geometric sum converges.
Now, we can see that $$\frac{(1+z)^{21}}{z(z^2+z+1)}$$ has simple poles at $$z=0$$, $$z= e^{\pm2\pi i/3}= \omega,\bar \omega$$. The residues are $$\text{res}_{z=0}\frac{(1+z)^{21}}{z(z^2+z+1)}=\lim_{z\to 0}\frac{(1+z)^{21}}{z^2+z+1}=1,$$ $$\text{res}_{z=\omega}\frac{(1+z)^{21}}{z(z^2+z+1)}=\lim_{z\to \omega}\frac{(1+z)^{21}}{z(z-\bar\omega)}=\frac{(\omega+1)^{21}}{\omega(\omega-\bar\omega)}=\frac{-\bar\omega^{21}}{\omega(\omega-\bar\omega)}=\frac{-1}{\omega(\omega-\bar\omega)},$$$$\text{res}_{z=\bar\omega}\frac{(1+z)^{21}}{z(z^2+z+1)}=\lim_{z\to \omega}\frac{(1+z)^{21}}{z(z-\omega)}=\frac{(\bar\omega+1)^{21}}{\bar\omega(\bar\omega-\omega)}=\frac{-\omega^{21}}{\bar\omega(\bar\omega-\omega)}=\frac{-1}{\bar\omega(\bar\omega-\omega)}.$$ Summing residues, we get $$1-\frac1{\omega-\bar\omega}(\frac{1}{\omega}-\frac{1}{\bar\omega})=1+\frac1{\omega\bar\omega}=2.$$ So we have that the expectation is equal to $$\frac{2}{20}=\frac{1}{10}.$$ (Note: the result can be confirmed by wolframalpha.)
In the book 'Concrete Mathematics' of Ronald L.Graham, Donald E.Knuth and Oren Patashnik you can find the value of $$R_m=\sum_{k\leq m}\binom{m-k}{k}(-1)^k.$$ Look at paragraph 5.2, Problem 3.
The authors shows that for $$m\geq 2$$ $$R_m=R_{m-1}-R_{m-2}$$ and finally got $$R_m=\begin{cases}\hphantom{-}1, & m \mod 6 = 0 \cr \hphantom{-}1, & m \mod 6 = 1 \cr \hphantom{-}0, & m \mod 6 = 2 \cr -1, & m \mod 6 = 3 \cr -1, & m \mod 6 = 4 \cr \hphantom{-}0, & m \mod 6 = 5\end{cases}$$ So the random variable $$X(N)=\sum_{k=0}^{N}{N-k \choose k}(-1)^k$$ can take only three values. And $$\mathbb P(X(N)=-1)=\mathbb P(N\in\{3,4,9,10,15,16\})=0.3,$$ $$\mathbb P(X(N)=0)=\mathbb P(N\in\{2,8,14,5,11,17\})=0.3,$$ $$\mathbb P(X(N)=1)=\mathbb P(N\in\{0,1,6,7,12,13,18,19\})=0.4.$$ So the expectation can be computed.