# The average of reciprocal binomials

This question is motivated by the MO problem here. Perhaps it is not that difficult.

Question. Here is an cute formula. $$\frac1n\sum_{k=0}^{n-1}\frac1{\binom{n-1}k}=\sum_{k=1}^n\frac1{k2^{n-k}}.$$ I've one justification along the lines of Wilf-Zeilberger (see below). Can you provide an alternative proof? Or, any reference?

The claim amounts to $a_n=b_n$ where $$a_n:=\sum_{k=0}^{n-1}\frac{2^n}{n\binom{n-1}k} \qquad \text{and} \qquad b_n:=\sum_{k=1}^n\frac{2^k}k.$$ Define $F(n,k):=\frac{2^n}{n\binom{n-1}k}$ and $\,G(n,k)=-\frac{2^n}{(n+1)\binom{n}k}$. Then, it is routinely checked that $$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k),\tag1$$ for instance by dividing through with $F(n,k)$ and simplifying. Summing (1) over $0\leq k\leq n-1$: \begin{align} \sum_{k=0}^{n-1}F(n+1,k)-\sum_{k=0}^{n-1}F(n,k) &=a_{n+1}-\frac{2^{n+1}}{n+1}-a_n, \\ \sum_{k=0}^{n-1}G(n,k+1)-\sum_{k=0}^{n-1}G(n,k) &=-\sum_{k=1}^n\frac{2^n}{(n+1)\binom{n}k}+\sum_{k=0}^{n-1}\frac{2^n}{(n+1)\binom{n}k}=0. \end{align} Therefore, $a_{n+1}-a_n=\frac{2^{n+1}}{n+1}$. But, it is evident that $b_{n+1}-b_n=\frac{2^{n+1}}{n+1}$. Since $a_1=b_1$, it follows $a_n=b_n$ for all $n\in\mathbb{N}$.

=====================================

Here is an alternative approach to Fedor's answer below in his elaboration of Fry's comment.

With $\frac1{n+1}\binom{n}k=\int_0^1x^{n-k}(1-x)^kdx$, we get $a_{n+1}=2^{n+1}\int_0^1\sum_{k=0}^nx^{n-k}(1-x)^kdx$. So, \begin{align} 2^{n+1}\int_0^1 dx\sum_{k=0}^nx^{n-k}(1-x)^k &=2^{n+1}\int_0^1x^ndx\sum_{k=0}^n\left(\frac{1-x}x\right)^k \\ &=2^{n+1}\int_0^1x^n\frac{\left(\frac{1-x}x\right)^{n+1}-1}{\frac{1-x}x-1}dx \\ &=\int_0^1\frac{(2-2x)^{n+1}-(2x)^{n+1}}{1-2x}\,dx:=c_{n+1}. \end{align} Let's take successive difference of the newly-minted sequence $c_{n+1}$: \begin{align} c_{n+1}-c_n &=\int_0^1\frac{(2-2x)^{n+1}-(2-2x)^n+(2x)^n-(2x)^{n+1}}{1-2x}\,dx \\ &=\int_0^1\left[(2-2x)^n+(2x)^n\right]dx=2^{n+1}\int_0^1x^ndx=\frac{2^{n+1}}{n+1}. \end{align} But, $b_{n+1}-b_n=\frac{2^{n+1}}{n+1}$ and hence $a_n=b_n$.

• I think that you should be able to proved it by using the identity $1/((n+1)\binom{n}{k}) = \int_0^1 x^{n-k}(1-x)^k dx$ and interchanging the summation and the integral. – user40023 Feb 19 '17 at 0:06
• If you simply want a reference, see (2.18) of math.wvu.edu/~gould/Vol.3.PDF. – Richard Stanley Feb 19 '17 at 1:27
• @RichardStanley: Thank you, indeed. It'd be a plus, too, if we can see different or novel proofs here. – T. Amdeberhan Feb 19 '17 at 1:34
• See, for instance, @robjohn's post at math.stackexchange.com/questions/151441/… – darij grinberg Feb 19 '17 at 2:21
• I wonder if there is a probabilistic interpretation. Choose a number $k$ from $[0,n-1]$, uniformly at random. Then choose a $k$-subset of $\lbrace 0,\ldots,n-1\rbrace$, uniformly at random. Then the left side is the probability you chose a leading subset of $\lbrace 0,\ldots,n-1\rbrace$. The question is how to interpret the right side as the same probability. – Brendan McKay Feb 19 '17 at 3:01

As in the question $$a_n:=\sum_{k=0}^{n-1}\frac{2^n}{n\binom{n-1}k} \qquad \text{and} \qquad b_n:=\sum_{k=1}^n\frac{2^k}k.$$ It is clear that $a_1=b_1$ and $b_{n+1}-b_n=\frac{2^{n+1}}{n+1}$. But we have the same recursive relation for $a_n$ because \begin{align} a_n&=2^n\sum_{k=0}^{n-1}\frac{k!(n-1-k)!(k+1+n-k)}{n!(n+1)} \\ &=2^n\sum_{k=0}^{n-1}\left(\frac{(k+1)!(n-1-k)!}{(n+1)!}+\frac{k!(n-k)!}{(n+1)!}\right) \\ &=2^n\left(2\sum_{k=0}^{n}\frac{k!(n-k)!}{(n+1)!}-\frac{2}{n+1}\right)=a_{n+1}-\frac{2^{n+1}}{n+1}. \end{align}
$$\frac1{2^{n+1}}\sum_{k=1}^{n+1}\frac{2^k}k=\frac1{2^{n+1}}\int_0^2(1+x+\dots+x^n)dx=\frac1{2^{n+1}}\int_0^2\frac{1-x^{n+1}}{1-x}dx=\\2\int_{0}^1\frac{(1/2)^{n+1}-t^{n+1}}{1-2t}dt=2\int_{0}^1\frac{(1-s)^{n+1}-(1/2)^{n+1}}{1-2s}ds.$$ We used change of variables $x=2t$, $s=1-t$. Now take a half-sum of two last expressions (identifying $t$ and $s$), you get $$\int_{0}^1\frac{(1-t)^{n+1}-t^{n+1}}{1-2t}dt=\sum_{k=0}^n\int_0^1(1-t)^kt^{n-k}dt=\sum_{k=0}^n\frac1{(n+1)\binom{n}k}.$$