Equivalent binomial forms

Question

In the book Concrete Mathematics 2ed by Knuth Graham and Patashnik there is an exercise 5.45. The exercise is the following

$$ \text { 45 Find a closed form for } \sum_{k \leqslant n}\left(\begin{array}{l}{2 k} \\ {k}\end{array}\right) 4^{-k} $$

From what they hint in the chapter this is a known identity that has a closed form of $\left(\begin{array}{c}{n+1 / 2} \\ {n}\end{array}\right)$. However they mention that one can use the parallel summation identity from the book to reach this answer. The parallel summation identity from the book is the following, $$ \sum_{k \leqslant n}\left(\begin{array}{c}{r+k} \\ {k}\end{array}\right)=\left(\begin{array}{c}{r+n+1} \\ {n}\end{array}\right), \quad \text { integer } n . \quad \text { parallel summation } $$

However this implies that the following should be true $$ \sum_{k \leqslant n}\binom{k-1/2}{k} =\sum_{k \leqslant n}\left(\begin{array}{l}{2 k} \\ {k}\end{array}\right) 4^{-k} $$

And I cannot see how this is true?

Answer 1

That formula is indeed correct. We can calculate that $\binom{k-1/2}{k}=\binom{2k}{k}4^{-k}$.

Indeed, by manipulating our expression, you can calculate \begin{align*} \binom{k-1/2}{k}&=\frac{\left(k-\frac{1}{2}\right)\left(k-1-\frac{1}{2}\right)\dots\left(\frac{1}{2}\right)}{k!}\\ &=\frac{\left(\frac{2k-1}{2}\right)\left(\frac{2k-3}{2}\right)\dots\left(\frac{1}{2}\right)}{k!}\\ &=\frac{(2k-1)(2k-3)\dots(1)2^{-k}}{k!}\cdot \frac{(2k)(2k-2)\dots2}{(2k)(2k-2)\dots2}\\ &=\frac{(2k)!}{k!}\cdot \frac{1}{(2k)(2k-2)\dots2}2^{-k}\\ &=\frac{(2k)!}{k!}\cdot \frac{1}{k(k-1)\dots1 \cdot 2^k}2^{-k}\\ &=\frac{(2k)!}{k!k!}2^{-2k}\\ &=\binom{2k}{k}4^{-k} \end{align*}

Answer 2

You can show the result using generating functions. Using the fact that $$ \binom{-1/2}{n}(-1)^n4^n=\binom{2n}{n} $$ combined with the binomial theorem yields that $$ \frac{1}{\sqrt{1-4x}}=\sum_{n=0}^\infty\binom{2n}{n}x^n. $$ In particular using the convolution of two generating functions we have that $$ \begin{align} \sum_{n=0}^\infty \binom{-3/2}{n}(-1)^n(4x)^n=(1-4x)^{-3/2}&=(1-4x)^{-1/2}\times (1-4x)^{-1}\\ &=\left(\sum_{n=0}^\infty \binom{2n}{n}x^n\right)\left(\sum_{n=0}^\infty 4^n x^n\right)\\ &=\sum_{n=0}^\infty\left(\sum_{k=0}^n\binom{2k}{k}4^{-k}\right)(4x)^n. \end{align} $$ Hence equating coefficients we have that $$ \sum_{k=0}^n\binom{2k}{k}4^{-k}=\binom{-3/2}{n}(-1)^n=\binom{3/2+n-1}{n}=\binom{n+1/2}{n} $$