14
$\begingroup$

Here is an identity for which I outlined two different arguments. I'm collecting further alternative proofs, so

QUESTION. can you provide another verification for the problem below?

Problem. Prove that $$\sum_{k=1}^n\binom{n}k\frac1k=\sum_{k=1}^n\frac{2^k-1}k.$$ Proof 1. (Induction). The case $n=1$ is evident. Assume the identity holds for $n-1$. Then, \begin{align*} \sum_{k=1}^{n+1}\binom{n+1}k\frac1k-\sum_{k=1}^n\binom{n}k\frac1k &=\frac1{n+1}+\sum_{k=1}^n\left[\binom{n+1}k-\binom{n}k\right]\frac1k \\ &=\frac1{n+1}+\sum_{k=1}^n\binom{n}{k-1}\frac1k \\ &=\frac1{n+1}+\frac1{n+1}\sum_{k=1}^n\binom{n+1}k \\ &=\frac1{n+1}\sum_{k=1}^{n+1}\binom{n+1}k=\frac{2^{n+1}-1}{n+1}. \end{align*} It follows, by induction assumption, that $$\sum_{k=1}^{n+1}\binom{n+1}k\frac1k=\sum_{k=1}^n\binom{n}k\frac1k+\frac{2^{n+1}-1}{n+1}=\sum_{k=1}^n\frac{2^k-1}k+\frac{2^{n+1}-1}{n+1} =\sum_{k=1}^{n+1}\frac{2^k-1}k.$$ The proof is complete.

Proof 2. (Generating functions) Start with $\sum_{k=1}^n\binom{n}kx^{k-1}=\frac{(x+1)^n-1}x$ and integrate both sides: the left-hand side gives $\sum_{k=1}^n\binom{n}k\frac1k$. For the right-hand side, let $f_n=\int_0^1\frac{(x+1)^n-1}x\,dx$ and denote the generating function $G(q)=\sum_{n\geq0}f_nq^n$ so that \begin{align*} G(q)&=\sum_{n\geq0}\int_0^1\frac{(x+1)^n-1}x\,dx\,q^n =\int_0^1\sum_{n\geq0}\frac{(x+1)^nq^n-q^n}x\,dx \\ &=\int_0^1\frac1x\left[\frac1{1-(x+1)q}-\frac1{1-q}\right]dx=\frac{q}{1-q}\int_0^1\frac{dx}{1-(x+1)q} \\ &=\frac{q}{1-q}\left[\frac{\log(1-(1+x)q)}{-q}\right]_0^1=\frac{\log(1-q)-\log(1-2q)}{1-q} \\ &=\frac1{1-q}\left[-\sum_{m=1}^{\infty}\frac1mq^m+\sum_{m=1}^{\infty}\frac{2^m}mq^m\right]=\frac1{1-q}\sum_{m=1}^{\infty}\frac{2^m-1}m\,q^m \\ &=\sum_{n\geq1}\sum_{k=1}^n\frac{2^k-1}k\,q^n. \end{align*} Extracting coefficients we get $f_n=\sum_{k=1}^n\frac{2^k-1}k$ and hence the argument is complete.

$\endgroup$
2
  • 4
    $\begingroup$ Is there a natural q-analog of this identity? $\endgroup$ Dec 20 '20 at 16:17
  • 1
    $\begingroup$ @PerAlexandersson I think yes, but too long for a comment. See my new answer. $\endgroup$ Dec 24 '20 at 17:12
5
$\begingroup$

$\DeclareMathOperator\lead{leader} \DeclareMathOperator\prob{prob}$Answering a follow-up question by Per Alexandersson. Here is the $q$-version obtained by a suitable modification of the probabilistic proof of the OP identity.

We consider the linear space $X:=\mathbb{F}_q^n$ over a finite field $\mathbb{F}_q$. For $x=(x_1,\ldots,x_n)\in X\setminus {0}$ denote $\lead(x)=\max(i:x_i\ne 0)$, for a subspace $L\subset X$, $m:=\dim L>0$, denote $\lead(L)=\max_{x\in L} \lead(x)$. It follows from Gauss elimination that $L$ contains a basis $f_1,\ldots,f_m$, such that $\lead(f_1)<\lead(f_2)<\ldots <\lead(f_m)=\lead(L)$. Thus $L$ contains exactly $q^m-q^{m-1}$ elements $x$ for which $\lead(x)=\lead(L)$, and $q^{m-1}$ 1-dimensional subspaces $R$ for which $\lead(R)=\lead(L)$.

Choose a random subspace $L$ of $X:=\mathbb{F}_q^n$ with probability of $k$-dimensional subspace proportional to $q^{k\choose 2} y^k$ ($k=1,2,\ldots,n$). The sum of these weights is $(1+y)(1+qy)\ldots (1+q^{n-1}y)-1:=\theta_n$ (that's $q$-binomial theorem).

Then choose a random 1-dimensional subspace $R\subset L$ uniformly. Consider the following probability: $\kappa:=\prob(\lead(R)=\lead(L))$. On one hand, $$ \kappa=\sum_{k=1}^n \prob(\dim L=k)\prob(\lead R=\lead L|\dim L=k)\\ =\theta_n^{-1}\sum_{k=1}^n q^{k\choose 2}y^k{n\choose k}_q\cdot \frac{q^{k-1}}{[k]_q}, $$ where $[k]_q=1+q+\ldots+q^{k-1}$ is the number of 1-dimensional subspaces of a $k$-dimensional space over $\mathbb{F}_q$.

On the other hand, denoting by $X_k$ the $k$-dimensional subspace of $x\in X$ for which $x_{k+1}=\ldots=x_n=0$, we get $$ \kappa=\sum_{k=1}^n \prob(L\subset X_k\& \lead(R)=k)=\sum_{k=1}^n \prob(L\subset X_k)\cdot \prob(\lead(R)=k|L\subset X_k)\\= \theta_n^{-1}\sum_{k=1}^n \theta_k\cdot \frac{q^{k-1}}{[k]_q}. $$

Thus the identity (we multiply both expressions for $\kappa$ by $q\cdot \theta_n$) $$ \sum_{k=1}^n q^{k+1\choose 2}y^k{n\choose k}_q\cdot \frac{1}{[k]_q}=\sum_{k=1}^n \frac{q^{k}((1+y)(1+qy)\ldots (1+q^{k-1}y)-1)}{[k]_q}, $$ for $q=y=1$ we get the initial identity.

$\endgroup$
34
$\begingroup$

$\DeclareMathOperator\prob{prob}$Alapan Das' clever argument may be rephrased on the probabilistic language. Write $[m]=\{1,2,\dotsc,m\}$. Choose a random non-empty subset $A\subset [n]$ (all $2^n-1$ possible outcomes having equal probabilities). Then choose a random element $\xi\in A$ uniformly. Denote $p=\prob (\xi=\max(A))$. On one hand, denoting $j=\lvert A\rvert$ we get $$ p=\sum_{j=1}^n \prob(\xi=\max(A)\mathrel||A|=j)\cdot \prob(|A|=j)=\sum_{j=1}^n\frac1j \cdot\frac{{n\choose j}}{2^n-1} $$

On the other hand, $$ p=\sum_{k=1}^n \prob(\xi=k \, \&\,A\subset [k])= \sum_{k=1}^n \prob(\xi=k\mathrel|A\subset [k])\cdot \prob(A\subset [k])\\= \sum_{k=1}^n \frac1k\cdot \frac{2^k-1}{2^n-1}. $$

$\endgroup$
3
  • 2
    $\begingroup$ This is beautiful! $\endgroup$ Dec 18 '20 at 20:12
  • $\begingroup$ Thank you Sam! I further simplified it. $\endgroup$ Dec 18 '20 at 20:35
  • 5
    $\begingroup$ @SamHopkins is not this simply obvious from the symmetry? All elements of $[k]$ have equal probabilities to be equal to $\xi$. $\endgroup$ Dec 18 '20 at 23:38
17
$\begingroup$

$$\sum_{k=1}^n\binom nk\frac1k=\sum_{k=1}^n\binom nk\int_0^1 dt\,t^{k-1}= \int_0^1 dt\,\sum_{k=1}^n\binom nk t^{k-1}=\int_0^1 dt\,\frac{(1+t)^n-1}t.$$ $$\sum_{k=1}^n\frac{2^k-1}k=\sum_{k=1}^n\int_0^1 dt\,(1+t)^{k-1}= \int_0^1 dt\,\sum_{k=1}^n (1+t)^{k-1}=\int_0^1 dt\,\frac{(1+t)^n-1}t.$$

$\endgroup$
5
  • 17
    $\begingroup$ To put it another way: $\sum_{k=1}^n \binom{n}{k} \frac{1}{k} = \sum_{k=1}^n \frac{2^k-1}{k}$ is a special case of $\sum_{k=1}^n \binom{n}{k} \frac{t^k}{k} = \sum_{k=1}^n \frac{(1+t)^k-1}{k}$ which is the antiderivative of $\sum_{k=1}^n \binom{n}{k} t^{k-1} = \sum_{k=1}^n (1+t)^{k-1}$, which follows from a combination of the binomial and geometric series identities. $\endgroup$
    – Terry Tao
    Dec 18 '20 at 17:20
  • 1
    $\begingroup$ @TerryTao : Thank you for your comment -- this is a good way to put it. $\endgroup$ Dec 18 '20 at 17:53
  • 3
    $\begingroup$ This can be rephrased combinatorially in a nice way: $\binom{n}{k}(k-1)!$ is the number of cyclic orderings of a $k$-element subset of $[n]$, so the first polynomial is the exponential generating function for cyclic orderings of subsets of $[n]$. On the other hand, $\frac{(1+t)^m-1}{m}$ is the exponential generating function for cyclic orders of subsets of $[m]$ whose largest element is $m$. I think that this is Fedor's proof in disguise. $\endgroup$ Dec 18 '20 at 22:37
  • $\begingroup$ @MartinRubey : Thank you for uncovering the connection with Fedor Petrov's answer. However, I certainly did not try to disguise anything. (Is that why my answer got the down vote?) In fact, my answer was given before Fedor's. $\endgroup$ Dec 20 '20 at 0:18
  • 2
    $\begingroup$ I find your answer very good, I certainly did not downvote it. English is not my first language, all I intended to say is that the two answers seem to be related. Put differently, also Fedor's proof seems to be your's in disguise. But in fact, I didn't try to make the relationship precise. (I also sometimes get downvotes I don't understand. It might happen by accident.) $\endgroup$ Dec 20 '20 at 9:34
16
$\begingroup$

\begin{align*} \sum_{k=1}^{n} \frac{2^k-1}{k} &=\sum_{k=1}^{n} \frac{1}{k}\left(\sum_{j=1}^{k} \binom{k}{j}\right) \\ &=\sum_{j=1}^{n} \sum_{k=j}^{n} \binom{k}{j}\frac{1}{k} \\ &=\sum_{j=1}^{n} \frac{1}{j}\left(\sum_{k=j}^{n} \binom{k-1}{j-1}\right) \\ &=\sum_{j=1}^{n} \frac{1}{j} \binom{n}{j}. \end{align*}

$\endgroup$
4
  • 2
    $\begingroup$ To me, this looks like a concise way to rewrite the induction proof in the OP. In particular, the last equality in your display is essentially the same as the identity $\binom nj-\binom{n-1}j=\binom{n-1}{j-1}$, used in the beginning of the induction proof, whereas your first equality is essentially what was used at the end of the the induction proof. $\endgroup$ Dec 18 '20 at 18:51
  • $\begingroup$ MathJax note: multi-line-equation AMS environments like {align*} work here, and display better than a collection of inline equations separated by blank lines. I have edited accordingly. $\endgroup$
    – LSpice
    Dec 18 '20 at 21:07
  • 1
    $\begingroup$ @IosifPinelis: I’d agree, in some sense this is essentially the same as the OP’s induction proof. But at the same time, this presentation is clearer and more informative in several ways — e.g. this version points the way more clearly to combinatorial/probabilistic interpretations such as that in Fedor Petrov’s answer. $\endgroup$ Dec 21 '20 at 16:16
  • $\begingroup$ @PeterLeFanuLumsdaine : I agree with your comment. $\endgroup$ Dec 21 '20 at 19:44
7
$\begingroup$

One can also use the binomial transform.

(If $A(z)=\sum_{i\geq 0} a_i z^i$ is a (formal) power series, the (formal) power series $B(z):=\frac{1}{1-z} A(\frac{z}{1-z})$ has coefficients $[z^n] B(z)=\sum_{j=0}^n {n \choose j} a_j$).

We have $\log(\frac{1}{1-z})=\sum_{k\geq 1} \frac{z^k}{k}$.

Thus \begin{align*} \sum_{k=1}^n {n \choose k}\frac{1}{k}&=[z^n] \frac{1}{1-z}\,\log\big(\frac{1}{1-\frac{z}{1-z}}\big)\\ &=[z^n] \frac{1}{1-z}\,\log\big(\frac{1-z}{1-2z}\big)\\ &=[z^n] \frac{1}{1-z}\,\Big(\log\big(\frac{1}{1-2z}\big)-\log\big(\frac{1}{1-z}\big)\Big)\\ &=\sum_{k=1}^n\frac{2^k}{k} -\sum_{k=1}^n \frac{1}{k}\end{align*}

$\endgroup$
5
$\begingroup$

Here's a sketch of a proof of a generalization: $$\sum_{k=1}^n\binom nk \frac{t^k}{k+a} =\frac{1}{\binom{a+n}{n}}\sum_{k=1}^n \binom {a+k-1}{k-1} \frac{(1+t)^k-1}{k}.\tag {$*$}$$ (This is a generalization of Terry Tao's generalization, which is the case $a=0$.)

We start with the identity $$\sum_{k=0}^n \binom nk \frac{t^k}{k+a} = \frac {1}{a\binom{a+n}{n}}\sum_{k=0}^n \binom{a+k-1}{k} (1+t)^k.$$ This is a special case of a well-known linear transformation for the hypergeometric series, the case $b=a+1$ of $${}_2F_1(-n,a; b\mid -t) =\frac{(b-a)_n}{(b)_n}\,_2F_1(-n,a; 1-n-b+a\mid 1+t),$$ where $(u)_n = u(u+1)\cdots (u+n-1)$, which can be proved easily in several ways.

Since $\frac{1}{a}\binom{a+k-1}{k} = \frac {1}{k}\binom{a+k-1}{k-1}$ for $k\ge 1$, we have $$\sum_{k=1}^n\binom nk \frac{t^k}{k+a} =\frac{1}{\binom{a+n}{n}}\sum_{k=1}^n \binom {a+k-1}{k-1} \frac{(1+t)^k-1}{k}+C$$ where $C$ is a constant (as a polynomial in $t$). But $C=0$ since each summand has no constant term in $t$, and $(*)$ follows.

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