# Alternative proofs sought after for a certain identity

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.

• Is there a natural q-analog of this identity? – Per Alexandersson Dec 20 '20 at 16:17
• @PerAlexandersson I think yes, but too long for a comment. See my new answer. – Fedor Petrov Dec 24 '20 at 17:12

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

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

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

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

• 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. – Terry Tao Dec 18 '20 at 17:20
• @TerryTao : Thank you for your comment -- this is a good way to put it. – Iosif Pinelis Dec 18 '20 at 17:53
• 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. – Martin Rubey Dec 18 '20 at 22:37
• @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. – Iosif Pinelis Dec 20 '20 at 0:18
• 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.) – Martin Rubey Dec 20 '20 at 9:34

\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*}

• 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. – Iosif Pinelis Dec 18 '20 at 18:51
• 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. – LSpice Dec 18 '20 at 21:07
• @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. – Peter LeFanu Lumsdaine Dec 21 '20 at 16:16
• @PeterLeFanuLumsdaine : I agree with your comment. – Iosif Pinelis Dec 21 '20 at 19:44

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*}

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.