# Chaitanya's Random Pages

## June 28, 2014

### A few sums involving inverses of binomial coefficients

Filed under: mathematics — ckrao @ 11:11 am

One of the problems from the 1990 Australian Mathematical Olympiad () asks one to prove the following result. $\displaystyle \sum_{k=1}^{2n-1}\frac{(-1)^{k-1}}{\binom{2n}{k}} = \frac{1}{n+1}.\quad\quad (1)$

One solution in  makes use of the following identity: \begin{aligned} \frac{1}{\binom{m}{k}} &= \frac{k!(m-k)!}{m!}\\ &= \frac{k!(m-k)!(m+1)(m+2)}{m!(m+1)(m+2)}\\ &= \left(\frac{m+1}{m+2}\right)\frac{k!(m-k)!(m+2)}{(m+1)!}\\ &= \left(\frac{m+1}{m+2}\right)\frac{k!(m-k)!((m-k+1) + (k+1))}{(m+1)!}\\ &=\left(\frac{m+1}{m+2}\right)\frac{k!(m-k+1)! + (k+1)!(m-k)!}{(m+1)!}\\ &= \frac{m+1}{m+2}\left(\frac{1}{\binom{m+1}{k}}+ \frac{1}{\binom{m+1}{k+1}}\right).\quad\quad(2) \end{aligned}

Then setting $m=2n$, (1) becomes a telescoping sum: \begin{aligned} \sum_{k=1}^{2n-1}\frac{(-1)^{k-1}}{\binom{2n}{k}} &= \sum_{k=1}^{2n-1} \frac{2n+1}{2n+2}\left(\frac{(-1)^{k-1}}{\binom{2n+1}{k}}+ \frac{(-1)^{k-1}}{\binom{2n+1}{k+1}}\right)\\ &= \frac{2n+1}{2n+2}\left( \sum_{k=1}^{2n-1} \frac{(-1)^{k-1}}{\binom{2n+1}{k}} + \sum_{k=1}^{2n-1} \frac{(-1)^{k-1}}{\binom{2n+1}{k+1}}\right)\\ &= \frac{2n+1}{2n+2}\left( \frac{(-1)^0}{\binom{2n+1}{1}} + \sum_{k=2}^{2n-1} \frac{(-1)^{k-1}}{\binom{2n+1}{k}} + \frac{(-1)^{2n-1-1}}{\binom{2n+1}{2n-1+1}} + \sum_{k=1}^{2n-2} \frac{(-1)^{k-1}}{\binom{2n+1}{k+1}} \right)\\ &= \frac{2n+1}{2n+2}\left( \frac{1}{2n+1} + \frac{1}{2n+1} + \sum_{k=1}^{2n-2} \frac{(-1)^{k}}{\binom{2n+1}{k+1}} + \sum_{k=1}^{2n-2} \frac{(-1)^{k-1}}{\binom{2n+1}{k+1}} \right)\\ &= \frac{2n+1}{2n+2} \left(\frac{2}{2n+1} + 0\right)\\ &= \frac{1}{n+1}. \end{aligned}

Using a similar argument one can prove the more general identity $\displaystyle \sum_{k=0}^n\frac{(-1)^k}{\binom{n}{k}} = \frac{n+1}{n+2}\left(1 + (-1)^n\right).\quad\quad (3)$

How about the sum $\displaystyle S(n) := \sum_{k=0}^{n}\frac{1}{\binom{n}{k}}$? Using (1) we find the recursion \begin{aligned} S(n) &= \frac{n+1}{n+2}\left(\sum_{k=0}^n \frac{1}{\binom{n+1}{k}} + \frac{1}{\binom{n+1}{k+1}}\right)\\ &= \frac{n+1}{n+2}\left(S(n+1)-1 + S(n+1)-1\right)\\ &= \frac{2(n+1)}{n+2}\left(S(n+1)-1 \right). \quad\quad (4)\\ \end{aligned}

Hence we have the recurrence relation $\displaystyle S(n+1) = \frac{n+2}{2(n+1)}S(n) + 1.\quad\quad(5)$

From this $S(n)$ does not have a closed form solution but using induction on n we can prove the following relations found in . $\displaystyle S(n) := \sum_{k=0}^{n}\frac{1}{\binom{n}{k}} = \frac{n+1}{2^{n+1}}\sum_{k=1}^{n+1}\frac{2^k}{k} = (n+1)\sum_{k=0}^n \frac{1}{(n+1-k)2^k}.\quad\quad(6)$

Firstly note that when $n=0$, the three expressions in (5) become $\frac{1}{\binom{0}{0}}$, $\frac{1}{2^{1}}\frac{2^1}{1}$ and $\frac{1}{1}$, which are all equal to 1. Hence (6) holds for $n=0$. Assume it holds for $n =m$. That is, $\displaystyle S(m) := \sum_{k=0}^{m}\frac{1}{\binom{m}{k}} = \frac{m+1}{2^{m+1}}\sum_{k=1}^{m+1}\frac{2^k}{k} = (m+1)\sum_{k=0}^m \frac{1}{(m+1-k)2^k}.\quad\quad(7)$

Then using (5), on the one hand, \begin{aligned} S(m+1) &= 1 + \frac{m+2}{2(m+1)}S(m)\\ &= 1 + \frac{m+2}{2(m+1)} \frac{m+1}{2^{m+1}}\sum_{k=1}^{m+1}\frac{2^k}{k} \\ &= 1 + \frac{m+2}{2^{m+2}}\sum_{k=1}^{m+1}\frac{2^k}{k}\\ &= \frac{(m+2)2^{m+2}}{2^{m+2}(m+2)} + \frac{m+2}{2^{m+2}}\sum_{k=1}^{m+1}\frac{2^k}{k}\\ &= \frac{m+2}{2^{m+2}}\sum_{k=1}^{m+2}\frac{2^k}{k},\quad\quad(8) \end{aligned}

while on the other, \begin{aligned}S(m+1) &= 1 + \frac{m+2}{2(m+1)}S(m)\\ &= 1 + \frac{m+2}{2(m+1)} (m+1)\sum_{k=0}^m \frac{1}{(m+1-k)2^k}\\ &= 1 + (m+2)\sum_{k=0}^m \frac{1}{(m+1-k)2^{k+1}}\\ &= 1 + (m+2)\sum_{k=0}^m \frac{1}{(m+2-(k+1))2^{k+1}}\\ &= 1 + (m+2)\sum_{k=1}^{m+1} \frac{1}{(m+2-k)2^{k}}\\ &= (m+2)\sum_{k=0}^{m+1} \frac{1}{(m+2-k)2^k}.\quad \quad(9) \end{aligned}

Equations (8) and (9) show that if (6) holds for $n=m$, then it does for $n=m+1$. By the principle of mathematical induction, (6) then is true for all integers $n\geq 0$.

Another related sum that can be expressed in terms of $S(n)$ is $\displaystyle \frac{1}{\binom{2n}{0}} + \frac{1}{\binom{2n}{2}} + \frac{1}{\binom{2n}{4}} + \ldots + \frac{1}{\binom{2n}{2n}}$. We have \begin{aligned}& \sum_{k=0}^{2n} \frac{1}{\binom{2n}{2k}}\\&= \frac{2n+1}{2n+2}\sum_{k=0}^{2n} \frac{1}{\binom{2n+1}{k}}\text{\quad \quad (by (5))}\\ &= \frac{2n+1}{2n+2} S(2n+1).\quad\quad(10) \end{aligned}

Note that more identities with inverses of binomial coefficients are in  (and references therein), where the integral $\displaystyle \frac{1}{\binom{n}{k}} = (n+1) \int_0^1 t^k (1-t)^{n-k}\ \text{d}t$

is utilised.

#### References

 A. W. Plank, Mathematical Olympiads: The 1990 Australian Scene, University of Canberra, 1990.

 T. Mansour, Combinatorial Identities and Inverse Binomial Coefficients, available at http://math.haifa.ac.il/toufik/toupap02/qap0204.pdf