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 ([1]) 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 [1] 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 [2].

\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 [2] (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

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

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

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: