How can I find $\sum\limits_{n=i+1}^\infty \binom{n-1}{i}\left (\frac{1}{3}\right)^{n}$?

Question

In a probability proof I've arrived at the sum $\sum\limits_{n=i+1}^\infty \binom{n-1}{i} \left(\frac{1}{3}\right)^{n}$ where $i$ is constant. WolframAlpha gives a simple expression for this sum, but I've been unable to find it myself: I've tried rewriting it as $\frac{1}{i!}\sum\limits_{n=i+1}^\infty \frac{(n-1)!}{(n-1-i)!} \left(\frac{1}{3}\right)^{n}$ but this hasn't advanced me much.

How can I find this sum?

Answer 1

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{\sum_{n\ =\ k + 1}^{\infty}{n - 1 \choose k}\pars{1 \over 3}^{n}:\ {\large ?}}$

---

$\Large\left.1\right)$ $$ \mbox{We'll use the identity}\quad \bbox[10px,border:1px dotted black]{\ds{{s \choose \ell} = \oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{s} \over z^{\ell + 1}} \,{\dd z \over 2\pi\ic}}} $$

\begin{align} &\sum_{n\ =\ k + 1}^{\infty}{n - 1 \choose k}\pars{1 \over 3}^{n} =\sum_{n\ =\ k + 1}^{\infty}\bracks{% \oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{n - 1} \over z^{k + 1}}\,{\dd z \over 2\pi\ic}} \pars{1 \over 3}^{n} \\[3mm]&={1 \over 3}\oint_{\verts{z}\ =\ 1}{1 \over z^{k + 1}}\bracks{% \sum_{n\ =\ k + 1}^{\infty}{\pars{1 + z \over 3}^{n - 1}}}\,{\dd z \over 2\pi\ic} \\[3mm]&={1 \over 3}\oint_{\verts{z}\ =\ 1}{1 \over z^{k + 1}}\bracks{% {\pars{1 + z}^{k}/3^{k} \over 1 - \pars{1 + z}/3}}\,{\dd z \over 2\pi\ic} ={1 \over 3^{k}}\,\half\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{k} \over z^{k + 1}} {1 \over 1 - z/2}\,{\dd z \over 2\pi\ic} \\[3mm]&={1 \over 3^{k}}\,\half\oint_{\verts{z}\ =\ 1} {\pars{1 + z}^{k} \over z^{k + 1}}\sum_{n = 0}^{\infty}\pars{z \over 2}^{n} \,{\dd z \over 2\pi\ic} ={1 \over 3^{k}}\,\half\sum_{n = 0}^{\infty}{1 \over 2^{n}}\oint_{\verts{z}\ =\ 1} {\pars{1 + z}^{k} \over z^{k - n+ 1}} \,{\dd z \over 2\pi\ic} \\[3mm]&={1 \over 3^{k}}\,\half\sum_{n = 0}^{k}{1 \over 2^{n}}{k \choose k - n} ={1 \over 3^{k}}\,\half\sum_{n = 0}^{k}{k \choose n}\pars{1 \over 2}^{n} ={1 \over 3^{k}}\,\half\pars{1 + \half}^{k} ={1 \over 2^{k + 1}} \end{align} $$ \bbox[10px,border:1px dotted black]{\ds{% \sum_{n\ =\ i + 1}^{\infty}{n - 1 \choose i}\pars{1 \over 3}^{n} = {1 \over 2^{i + 1}}}} $$

---

$\Large\left.2\right)$ \begin{align} \sum_{n\ =\ i + 1}^{\infty}{n - 1 \choose i}\pars{1 \over 3}^{n} & = \sum_{n\ =\ 0}^{\infty}{n + i \choose i}\pars{1 \over 3}^{n + i + 1} = \pars{1 \over 3}^{i + 1} \sum_{n\ =\ 0}^{\infty}{n + i \choose n}\pars{1 \over 3}^{n} \\[5mm] & = \pars{1 \over 3}^{i + 1} \sum_{n\ =\ 0}^{\infty}\bracks{{-i - 1 \choose n}\pars{-1}^{n}} \pars{1 \over 3}^{n} \\[5mm] & = \pars{1 \over 3}^{i + 1} \sum_{n\ =\ 0}^{\infty}{-i - 1 \choose n}\pars{-\,{1 \over 3}}^{n} = \pars{1 \over 3}^{i + 1}\bracks{1 + \pars{-\,{1 \over 3}}}^{-i - 1} \\[5mm] & = \bbox[10px,border:1px dotted black]{\ds{1 \over 2^{i + 1}}} \end{align}

Answer 2

Using Grigory's Wiki link, we wish to adjust our sum to start at zero.

Find $m$ such that $n = i+1$ implies $m=0$: $m = n-(i+1) = n-i-1.$ Now adjust the term inside the binomial coefficient. Since $n = m+i+1$, then $n-1 = m+i$.

Therefore,

$$\sum_{n=i+1}^\infty \begin{pmatrix} n-1 \\ i\end{pmatrix} \left(\frac13\right)^n = \sum_{m=0}^\infty \begin{pmatrix} m+i \\ i \end{pmatrix}\left(\frac13\right)^{m+i+1}.$$

Now, $i$ is fixed inside the sum. So let's re-write:

$$\sum_{m=0}^\infty \begin{pmatrix} m+i \\ i \end{pmatrix}\left(\frac13\right)^{m+i+1} = \left(\frac13\right)^{i+1}\sum_{m=0}^\infty \begin{pmatrix} m+i \\ i \end{pmatrix}\left(\frac13\right)^m.$$

The binomial coefficient is symmetric, in other words

$$\begin{pmatrix} p \\ q \end{pmatrix} = \frac{p!}{q!(p-q)!} = \frac{p!}{(p-q)!(p-(p-q))!} = \begin{pmatrix} p \\ p-q\end{pmatrix}.$$

Therefore, $$\begin{pmatrix} m+i \\ i\end{pmatrix} = \begin{pmatrix} m+i \\ m+i-i \end{pmatrix} = \begin{pmatrix} m+i \\ m \end{pmatrix}.$$

Now our series becomes

$$\begin{align*} \left(\frac13\right)^{i+1}\sum_{m=0}^\infty \begin{pmatrix} m+i \\ i \end{pmatrix}\left(\frac13\right)^m &= \left(\frac13\right)^{i+1}\sum_{m=0}^\infty \begin{pmatrix} m+i \\ m \end{pmatrix}\left(\frac13\right)^{m} \\ &= \frac{\left(\frac13\right)^{i+1}}{\left(1-\frac13\right)^{i+1}}\\ &= \frac{\left(\frac13\right)^{i+1}}{\left(\frac23\right)^{i+1}} \\ &= 2^{-i-1}. \end{align*}$$

Note that the second step uses the special case linked in the Wiki article.

Answer 3

This is a generating function approach.

Let $$S_i(z)=\sum_{n=i}^\infty \binom n i z^i$$

The number you are looking for is $\frac{1}{3}S_i\left(\frac 1 3\right)$.

Let $$\begin{align} T(w,z) &= \sum_{i=0}^\infty S_i(z)w^i \\&= \sum_{i=0}^\infty \sum_{n=i}^\infty \binom n i w^iz^n \\ &=\sum_{n=0}^\infty \sum_{i=0}^n \binom n i w^iz^n \\ &=\sum_{n=0}^\infty z^n(1+w)^n = \\ &=\frac{1}{1-z(1+w)}\\ &=\frac{1}{1-z}\frac{1}{1-w\frac{z}{1-z}}\\ &=\frac{1}{1-z}\sum_{i=0}^\infty \left(\frac{z}{1-z}\right)^iw^i \end{align}$$

This means that $$S_i(z)=\frac{1}{1-z}\left(\frac z {1-z}\right)^i$$

The value you want is $zS_i(z) = \left(\frac z {1-z}\right)^{i+1}$, with $z=\frac 1 3$, $\frac z {1-z} = \frac 1 2$, so the answer should be $$\frac{1}{2^{i+1}}$$

Answer 4

Use the identity $${k\choose n}={k+1\choose n+1}-{k\choose n+1}$$ and let $$S_n = \sum_{k\geqslant n}{k\choose n}x^{k}$$ to get

$$S_n=\sum_{k\geqslant n+1}{k\choose n}x^{k}+\color{Red}{x^n}= \sum_{k\geqslant n+1}{k+1\choose n+1}x^k-\sum_{k\geqslant n+1}{k\choose n+1}x^k+\color{Red}{x^n}\\= \color{Red}{x^{-1}}\left(\color{Blue}{\sum_{k\geqslant n+1}{k\choose n+1}x^k}-\color{Red}{x^{n+1}}\right)-\color{Blue}{\sum_{k\geqslant n+1}{k\choose n+1}x^k}+\color{Red}{x^n}\\=(x^{-1}-1)\color{Blue}{S_{n+1}}.$$ That way, $$\frac{S_n}{S_0}=\prod_{k=0}^{n-1}\frac{S_{k+1}}{S_k}=\left(\frac{1}{x^{-1}-1}\right)^n.$$ We know $S_0=\frac{1}{1-x}$, so $$S_n=\sum_{k\geqslant n}{k\choose n}x^k=x^{-1}\left(\frac{1}{x^{-1}-1}\right)^{n+1}.$$