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

2 Answers 2

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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