Uniform distribution variable in the Newton symbol

Question

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.

Please help

Answer 1

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.)

Answer 2

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.