"Skipped" binomial distribution sum

Question

How can I show that

$$\sum_{i=0}^{N/K-1} {N \choose iK+j} p^{iK+j}(1-p)^{N-iK-j}=\frac{1}{K},$$

where $N\rightarrow \infty$, $0\le j< K$, and $K$ is finite?

Answer 1

Finally got it after some more thought. I am following the suggestion by kimchi lover. Let $f[n]={N \choose n} p^n (1-p)^{N-n}$ and $g[n]=\begin{cases} 1 & \mbox{ if } n \mod K \equiv j \\ 0 & \mbox{otherwise}\end{cases}$. Note that the sum is just $$\sum_{n=0}^N f[n] g[n]=\mathcal{F}(fg)[k]|_{k=0},$$ where $\mathcal{F}(f)[k]=\sum_{n=0}^{N-1} f[n] e^{-i\frac{2 \pi k n }{N}}$ is the discrete Fourier transform of length-$N$. For convenience, we will use upper case letter to denote the Fourier transform. That is, $F[k] \triangleq \mathcal{F}(f)[k]$. And the inverse transform will then be given by $\mathcal{F}^{-1}(F)[n]=\frac{1}{N}\sum_{k=0}^{N-1} F[k] e^{i\frac{2\pi n k}{N}}$.

Now, it is easy to verify that product in Fourier domain will correspond to convolution in the original domain and vice versa. More precisely, we have $$ \mathcal{F}(fg)= \frac{1}{N} F \circledast G$$

Without loss of generality, we will assume $N$ is divisible by $K$ and $N=K N'$. Let's try to find $F[k]$ and $G[k]$. For $F[k]$, $$F[k]=\sum_{n=0}^{N-1} {N \choose n} (1-p)^{N-n} (pe^{-i\frac{2\pi k}{N}})^n = (1-p+pe^{-i\frac{2\pi k}{N}})^N.$$

For $G[k]$, first consider the case when $j=0$, let $g_0[n]=\begin{cases} 1 & \mbox{ if } n \mod K \equiv 0 \\ 0 & \mbox{otherwise}\end{cases}$. One can verify that $G_0[k]$ is simply $$ G_0[k]=\begin{cases} N' & \mbox{ if } k \mod N' \equiv 0 \\ 0 & \mbox{otherwise}\end{cases}.$$ Now for $j \neq 0$, $g[n] $ is just a shift of $g_0[n]$ by $j$ samples. Thus $$ G[k]=\begin{cases} N' e^{i\frac{2\pi j k}{N}}& \mbox{ if } k \mod N' \equiv 0 \\ 0 & \mbox{otherwise}\end{cases}.$$

Finally, the sum is then \begin{align*} \mathcal{F}(fg)[k]|_{k=0}&= \frac{1}{N} F \circledast G[k]|_{k=0} = \frac{1}{N}\sum_{k'=0}^{N-1} F[k'] G[k-k']|_{k=0} = \frac{1}{N}\sum_{k'=0}^{N-1} F[k'] G[-k'] \\ &= \frac{1}{N} \sum_{m=0}^{K} (1-p+pe^{-i\frac{2\pi N' m }{N}})^N N' e^{-i\frac{2\pi j N' m}{N}} \\ &= \frac{1}{K} \sum_{m=0}^{K} (1-p+pe^{-i\frac{2\pi m }{K}})^N e^{-i\frac{2\pi j m}{K}} \\ &= \frac{1}{K}, \mbox{as $N$ goes to infinity}, \end{align*} where the last equality is due to the fact that $(1-p+pe^{-i\frac{2\pi m }{K}})$ has magnitude less than 1 except when $m=0$. So as $N$ goes to infinity, only the first term in the sum is non-zero.

Some final words. The scenario in this setup is analogous to sampling above Nyquist rate in digital signal processing. There is no aliasing and "copies" from higher frequency band does not mix up with the baseband.

Answer 2

With $\binom{n}{r}=\oint\frac{(1+z)^n}{z^r}\frac{dz}{2\pi\operatorname{i}z}$ (with the centre-$O$ unit circle as the contour), the sum is$$\begin{align}&\sum_{i\ge0}\oint\frac{(1+z)^N}{z^{iK+j}}p^{iK+j}(1-p)^{N-iK-j}\frac{dz}{2\pi\operatorname{i}z}\\&=\sum_{i\ge0}\oint((1-p)(1+z))^N\left(\frac{p}{(1-p)z}\right)^{iK+j}\frac{dz}{2\pi\operatorname{i}z}\\&=\oint((1-p)(1+z))^N\left(\frac{p}{(1-p)z}\right)^j\frac{1}{1-\left(\frac{p}{(1-p)z}\right)^K}\frac{dz}{2\pi\operatorname{i}z}\\&=p^j(1-p)^{N+K-j}\oint\frac{(1+z)^Nz^{K-j-1}}{(1-p)^Kz^K-p^K}\frac{dz}{2\pi\operatorname{i}}.\end{align}$$The poles are all first-order, at $\frac{p}{1-p}\exp\frac{2\pi\operatorname{i}l}{K}$ for $0\le l<K$, so the above expression is$$p^j(1-p)^{N+K-j}\sum_{l=0}^{K-1}\left.\frac{(1+z)^Nz^{-j}}{K(1-p)^K}\right|_{z=\frac{p}{1-p}\exp\frac{2\pi\operatorname{i}l}{K}}\\=\frac1K\sum_l\frac{\left(1-p+p\exp\frac{2\pi\operatorname{i}l}{K}\right)^N}{\exp\frac{2\pi\operatorname{i}jl}{K}}.$$In the $N\to\infty$ limit only $l=0$ survives, making the sum $1$.