Exercise 1.4.23* (Conundrum 5/8)

beginproof

(a)

By Exercise 7, for $|z|<1$, $$\frac{1}{{(1-z)}^{n+1}}=\underset{k=0}{\overset{\infty }{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n}{k}\right)z^k.$$

If we take $z=1∕2$ in this formula, we obtain

$$\underset{k=0}{\overset{\infty }{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n}{k}\right)2^{-k}=\frac{1}{{(1-(1∕2))}^{n+1}}=2^{n+1}.$$

(b)

Induction is the key! We search a relation between $S_n$ and $S_{n+1}$, where $$S_n=\underset{k=0}{\overset{n}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n}{k}\right)2^{-k}=\underset{k=0}{\overset{n}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n}{n}\right)2^{-k},$$

and

$$S_{n+1}=\underset{k=0}{\overset{n+1}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n+1}{n+1}\right)2^{-k}.$$

Using the Pascal relation

$$\left(\genfrac{}{}{0.0pt}{}{k+n}{n}\right)+\left(\genfrac{}{}{0.0pt}{}{k+n}{n+1}\right)=\left(\genfrac{}{}{0.0pt}{}{k+n+1}{n+1}\right),$$

we obtain

$$\begin{array}{llll}\hfill S_n& =1+\underset{k=1}{\overset{n}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n}{n}\right)2^{-k}& \hfill & \\ \hfill & =1+\underset{k=1}{\overset{n}{\sum }}\left(\left(\genfrac{}{}{0.0pt}{}{k+n+1}{n+1}\right)-\left(\genfrac{}{}{0.0pt}{}{k+n}{n+1}\right)\right)2^{-k}& \hfill & \\ \hfill & =1+\underset{k=1}{\overset{n}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n+1}{n+1}\right)2^{-k}-\underset{k=1}{\overset{n}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n}{n+1}\right)2^{-k}& \hfill & \\ \hfill & =1+\underset{k=1}{\overset{n}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n+1}{n+1}\right)2^{-k}-\underset{K=0}{\overset{n-1}{\sum }}\left(\genfrac{}{}{0.0pt}{}{K+n+1}{n+1}\right)2^{-K-1}(K=k-1)& \hfill & \\ \hfill & =1+\underset{k=1}{\overset{n}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n+1}{n+1}\right)2^{-k}-\underset{k=0}{\overset{n}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n+1}{n+1}\right)2^{-k-1}+\left(\genfrac{}{}{0.0pt}{}{2n+1}{n+1}\right)2^{-n-1}& \hfill & \\ \hfill & =\frac{1}{2}+\underset{k=1}{\overset{n}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n+1}{n+1}\right)\left(2^{-k}-2^{-k-1}\right)+\left(\genfrac{}{}{0.0pt}{}{2n+1}{n+1}\right)2^{-n-1}& \hfill & \\ \hfill & =\frac{1}{2}\left(1+\underset{k=1}{\overset{n}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n+1}{n+1}\right)2^{-k}+\left(\genfrac{}{}{0.0pt}{}{2n+1}{n+1}\right)2^{-n}\right)& \hfill & \\ \hfill & =\frac{1}{2}\left(\underset{k=0}{\overset{n}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n+1}{n+1}\right)2^{-k}+2\left(\genfrac{}{}{0.0pt}{}{2n+1}{n+1}\right)2^{-n-1}\right)& \hfill & \\ \hfill & =\frac{1}{2}\left(\underset{k=0}{\overset{n}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n+1}{n+1}\right)2^{-k}+\left(\genfrac{}{}{0.0pt}{}{2n+2}{n+1}\right)2^{-n-1}\right)& \hfill & \\ \hfill & =\frac{1}{2}\underset{k=0}{\overset{n+1}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n+1}{n+1}\right)2^{-k}& \hfill & \\ \hfill & =\frac{1}{2}{S}_{n+1},& \hfill & \end{array}$$ because $$\left(\genfrac{}{}{0.0pt}{}{2n+2}{n+1}\right)=\frac{(2n+2)!}{(n+1)!(n+1)!}=\frac{2n+2}{n+1}\frac{(2n+1)!}{(n+1)!n!}=2\left(\genfrac{}{}{0.0pt}{}{2n+1}{n+1}\right).$$

So $S_{n+1}=2S_n$ for all $n\in \mathbb{N}$, and $S_0=1$. Therefore $S_n=2^n$. That is

$$\underset{k=0}{\overset{n}{\sum }}\left(\genfrac{}{}{0.0pt}{}{k+n}{k}\right)2^{-k}=2^n.$$