Show that $\lim_{n \rightarrow \infty} \frac{\Sigma_{i=0}^k \binom{n}{3i}}{2^n} = \frac{1}{3}$

Question

Let $n = 3k$ . Show that $\displaystyle{\lim\limits_{n \rightarrow \infty} \frac{\Sigma_{i=0}^k \binom{n}{3i}}{2^n} = \frac{1}{3}}$ . In other words, the sum of every third element of the nth row of the Pascal triangle is roughly one third of the sum of all elements of that row; after this, generalize the result.

attempt:

$\displaystyle{\begin{array}{ll} \lim\limits_{n \rightarrow \infty} \displaystyle{\frac{\Sigma_{i=0}^k \binom{3k}{3i}}{2^n}} & = \\\\ \lim\limits_{n \rightarrow \infty} \displaystyle{\frac{\binom{3k}{0} + \binom{3k}{3} + \binom{3k}{6} + \cdot \cdot \cdot + \binom{3k}{k} }{2^n}} & = \\\\ \lim_\limits{n \rightarrow \infty} \displaystyle{\frac{\frac{3k!}{0! 3k!} + \frac{3k!}{3!(3k-3)!} + \frac{3k!}{6!(3k-6)!} + \cdot \cdot \cdot + \frac{3k!}{3k!(3k - 3k)!} }{2^n}} & = \\\\ \lim_\limits{n \rightarrow \infty} \displaystyle{\frac{\frac{1}{1} + \frac{3k (3k-1)(3k-2)(3k-3)....2 \cdot 1}{3!(3k-3)!} + \frac{3k(3k-1)(3k-2)...(3k-6)...2.1}{6!(3k-6)!} + \cdot \cdot \cdot + \frac{1}{1} }{2^n}} & = \\\\ \lim_\limits{n \rightarrow \infty} \displaystyle{\frac{\frac{1}{1} + \frac{3k (3k-1)(3k-2)(3k-3)}{3!} + \frac{3k(3k-1)(3k-2)...(3k-5)}{6!} + \cdot \cdot \cdot + \frac{1}{1} }{2^n}} \end{array}}$

I am stuck. If $n = 3k$ approaches infinity then it seems that we would have $0$ on the numerator and so the expression would go to $0$ and not $1/3$ .
Could someone please help me ? and give me some feedback. Thank you

Answer 1

Let $\omega=\exp\left(\frac{2\pi i}{3}\right)$. The characteristic function of the integers $n$ of the form $3k$ can be written as $\frac{1+\omega^n+\omega^{2n}}{3}$ (this is the principle behind the discrete Fourier transform) hence

$$ \sum_{i\geq 0}\binom{n}{3i} = \frac{1}{3}\sum_{k=0}^{n}\binom{n}{k}(1+\omega^k+\omega^{2k})=\frac{2^n+(1+\omega)^n+(1+\omega^2)^n}{3}$$ and accidentally both $1+\omega$ and $1+\omega^2$ have unit modulus, hence the term $(1+\omega)^n+(1+\omega^2)^n$ is bounded by $2$ in modulus, regardless of $n$. It follows that $$ \lim_{n\to +\infty}\frac{1}{2^n}\sum_{i\geq 0}\binom{n}{3i}=\color{red}{\frac{1}{3}} $$ as wanted. In other terms,

If we consider a random subset of $\{1,\ldots,n\}$, its cardinality equals $3k$ for some $k\in\mathbb{N}$
with a probability closer and closer to $\frac{1}{3}$ as $n$ increases.

That holds also if $3$ is replaced by $4,5,6,7,\ldots$, but the speed of convergence is quite different:
to prove it (through the DFT) is an interesting exercise I leave to the reader / to the OP.

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

As $\ds{k \to \infty}$:

\begin{align} {1 \over 8^{k}}\sum_{i = 0}^{k}{3k \choose 3i} & \sim {1 \over 8^{k}}\sum_{i = 0}^{k} {3k \choose 3k/2}\exp\pars{-\,{6\bracks{i - k/2}^{2} \over k}} \\[5mm] & \sim \root{\pi \over 6}{k^{1/2} \over 8^{k}}{3k \choose 3k/2} \to \bbx{\ds{{1 \over 3}\quad\mbox{as}\ k \to \infty}} \end{align}

That is an application of 'Laplace Method for Sums' as explained in, for example, page $761$ of $\ds{\bbox[8px,#efe,border:1px dotted navy]{Analytic\ Combinatorics}}$ by Philipe Flajolet and Robert Sedgewick, Cambridge University Press 2009.