8
$\begingroup$

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$.

$\endgroup$
  • 8
    $\begingroup$ 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. $\endgroup$ – user40023 Feb 19 '17 at 0:06
  • 3
    $\begingroup$ If you simply want a reference, see (2.18) of math.wvu.edu/~gould/Vol.3.PDF. $\endgroup$ – Richard Stanley Feb 19 '17 at 1:27
  • $\begingroup$ @RichardStanley: Thank you, indeed. It'd be a plus, too, if we can see different or novel proofs here. $\endgroup$ – T. Amdeberhan Feb 19 '17 at 1:34
  • $\begingroup$ See, for instance, @robjohn's post at math.stackexchange.com/questions/151441/… $\endgroup$ – darij grinberg Feb 19 '17 at 2:21
  • 1
    $\begingroup$ 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. $\endgroup$ – Brendan McKay Feb 19 '17 at 3:01
7
$\begingroup$

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}

$\endgroup$
7
$\begingroup$

Let me elaborate on Fry's suggestion and your forthcoming comment.

$$\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}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.