Find the limit of a finite sum involving binomial coefficients

Question

I am trying to evaluate the following limit, where $n$ and $q$ are non-negative integers, and $n > q$. $$\lim_{m→∞}{\frac{1}{2^m}}∑_{k}{m\choose{nk+q}} $$ Does it exist? If so, what is the value?

Answer 1

Your summation is exactly $\lim_{m\to\infty}P(X_m\equiv q\pmod n)$, where $X_m\sim \text{Bin}(m,\frac12)$.

We can write $X_m=Y_1+Y_2+\dots+Y_m$, where $Y_i$ are independent $\{0,1\}$ coin flips. Doing so, the value of $X_m\pmod n$ is a Markov chain which is irreducible and aperiodic, so $X_m\pmod n$ converges to a unique stationary distribution. Since it is clear that the uniform distribution on $\{0,1,\dots,n-1\}$ is a stationary distribution of this process (if $X\sim \text{Unif}(\mathbb Z/n\mathbb Z)$ and $Y$ is any $\mathbb Z/n\mathbb Z$-valued random variable, then $X+Y$ is also $\text{Unif}(\mathbb Z/n\mathbb Z)$), it follows that $P(X_m\equiv q\pmod n)\to \frac1n$ as $m\to\infty$.

Answer 2

By the binomial theorem and the discrete Fourier transform $$ \sum_{k\equiv q\!\pmod{\!\!n}}\binom{m}{k} = \frac{1}{n}\left[2^m+\sum_{h=1}^{n-1}c_h (1+\zeta_n^h)^m\right]$$ with $\zeta_n=\exp\left(\frac{2\pi i}{n}\right)$ and $c_h\in S^1$. It follows that the wanted limit is $\frac{1}{n}$, proving that

The distribution of the subsets of $\{1,\ldots,m\}$ according to the residue class $\!\!\pmod{n}$ of their cardinality is approximately uniform.