# How to prove $\sum_{k=1}^n{n\choose k}\frac{(-1)^{k+1}}{k}=\sum_{k=1}^n\frac{1}{k}$?

I think by induction we can do it. Let $$I(n)=\sum_{k=1}^n{n\choose k}\frac{(-1)^{k+1}}{k}=\sum_{k=1}^n\frac{1}{k}.$$ Then, we must show that $$I(n+1)-I(n)=\frac{1}{n+1}$$.

\begin{align} I(n+1)-I(n)&=\frac{(-1)^{n+1}}{n+1}+\sum_{k=1}^n\left({n+1\choose k}-{n\choose k}\right)\frac{(-1)^{k+1}}{k}\\ &=I(n+1)-I(n)=\frac{(-1)^{n+1}}{n+1}+\sum_{k=1}^n{n\choose k-1}\frac{(-1)^{k+1}}{k}\\ &=\frac{(-1)^{n+1}}{n+1}-\frac{1}{n+1}\sum_{k=1}^n{n+1\choose k}(-1)^{k}\\ &=\frac{(-1)^{n+1}}{n+1}+\frac{(-1)^n+1}{n+1}\\ &=\frac{1}{n+1} \end{align}

I saw these steps now. If you don't write you can't see anything. Thanks for help and elementary proofs.

WA says it is about Digamma function. What is the connection? These are very hot topics for students like me.

• I will say that a more elementary proof of this statement, in the style of your attempt, does exist. Here is a proof of a generalization of this identity I authored a while back, in case you're interested. Commented Jan 8, 2023 at 22:50
• @C-RAM Thanks I will try it. Commented Jan 8, 2023 at 23:09
• For a standard non-elementary solution (i.e. using calculus) see chapter 2 in en.wikipedia.org/wiki/Harmonic_number Commented Jan 9, 2023 at 19:31

$$(1 + x)^n = \sum_{k=0}^n {n \choose k} x^k.$$

We want to modify this so that the $$x^k$$ term becomes $$(-1)^{k+1} x^{k-1}$$, so that we can integrate it. This means the LHS is

$$I_n = \int_0^1 \frac{1 - (1 - x)^n}{x} \, dx.$$

Now perform the substitution $$u = 1 - x$$, which gives

$$I_n = \int_0^1 \frac{1 - u^n}{1 - u} \, du = \int_0^1 \left( 1 + u + \dots + u^{n-1} \right) \, du = \sum_{k=1}^n \frac{1}{k} = H_n$$

which is the RHS, as desired.

An alternative argument, also using generating functions, in a different way. We need the following general facts: if a sequence $$\{ a_k \}$$ has generating function $$A(x) = \sum a_k x^k$$, then

1. The generating function of the partial sums $$\sum_{k=0}^n a_k$$ is $$\frac{1}{1 - x} A(x)$$, and
2. The generating function of the binomial sums $$\sum_{k=0}^n {n \choose k} a_k$$ is $$\frac{1}{1 - x} A \left( \frac{x}{1 - x} \right)$$ (this is a nice exercise).

Now, the generating function of the sequence $$\frac{(-1)^{k+1}}{k}$$ is $$\ln (1 + x)$$, and the generating function of the sequence $$\frac{1}{k}$$ is $$\ln \frac{1}{1 - x}$$. This gives that the generating function of the LHS is

$$\frac{1}{1 - x} \ln \left( 1 + \frac{x}{1 - x} \right) = \frac{1}{1 - x} \ln \frac{1}{1 - x}$$

which is also the generating function of the RHS.

• Elementary... Thanks. Commented Jan 8, 2023 at 22:45
• Is this a Mobius transformation? Commented Jan 8, 2023 at 22:52
• The bit on the inside is, yes. Commented Jan 8, 2023 at 23:18

You got off to a good start. Now use

$$\binom n{k-1}\frac1k=\binom{n+1}k\frac1{n+1}\;$$

to obtain

$$\begin{eqnarray} \sum_{k=1}^n\binom n{k-1}\frac{(-1)^{k+1}}k &=& \sum_{k=1}^n\binom {n+1}k\frac{(-1)^{k+1}}{n+1} \\ &=& \frac1{n+1}\left(1-(-1)^n-\sum_{k=0}^{n+1}\binom {n+1}k(-1)^k\right) \\ &=& \frac1{n+1}\left(1-(-1)^n-(1+(-1))^{n+1}\right)\\ &=& \frac1{n+1}-(-1)^n\frac1{n+1}\;. \end{eqnarray}$$

You have the wrong sign on your $$n+1$$ term; if you correct that, it cancels with the second term here, leaving $$\frac1{n+1}$$ as required.

• +1 This is the only elementary solution up to now here. Commented Jan 9, 2023 at 19:31

$$\sum_{k=1}^n\binom{n}{k}\frac{(-1)^{k-1}}{k^{a}}=\sum_{k=1}^n \binom{n}{k}(-1)^{k-1}\int_0^1 \frac{(-1)^{a-1}}{(a-1)!} x^{k-1}\ln^{a-1}(x)dx$$

$$=\frac{(-1)^{a-1}}{(a-1)!}\int_0^1\left(\sum_{k=1}^n \binom{n}{k}(-x)^{k-1}\right)\ln^{a-1}(x)dx$$

$$=\frac{(-1)^{a-1}}{(a-1)!}\int_0^1\left(\frac{1-(1-x)^n}{x}\right)\ln^{a-1}(x)dx$$

$$\overset{1-x\to x}{=}\frac{(-1)^{a-1}}{(a-1)!}\int_0^1\frac{1-x^n}{1-x}\ln^{a-1}(1-x)dx$$

$$\overset{IBP}{=}\frac{(-1)^a n}{a!}\int_0^1 x^{n-1}\ln^a(1-x)dx$$

$$=\frac{(-1)^a n}{a!} t(a,n)$$

where

$$t(a,n)=\lim_{m\to1}\frac{\partial^a}{\partial m^a}\operatorname{B}(m,n)$$

$$=(-1)^a(a-1)!\left[\frac{H_n^{(a)}}{n}+\sum_{j=1}^{a-1}\frac{(-1)^j}{j!}H_n^{(a-j)}t(j,n)\right],\quad a=1,2,3...$$

For $$a=1$$,

$$\sum_{k=1}^n\binom{n}{k}\frac{(-1)^{k-1}}{k}=-nt(1,n)=H_n$$

For $$a=2$$,

$$\sum_{k=1}^n\binom{n}{k}\frac{(-1)^{k-1}}{k^2}=\frac{n}2 t(2,n)=\frac{1}2\left(H_n^2+H_n^{(2)}\right)$$

For $$a=3$$,

$$\sum_{k=1}^n\binom{n}{k}\frac{(-1)^{k-1}}{k^3}=-\frac{n}6t(3,n)=\frac{1}6\left(H_n^3+3H_nH_n^{(2)}+2H_n^{(3)}\right)$$

For $$a=4$$,

$$\sum_{k=1}^n\binom{n}{k}\frac{(-1)^{k-1}}{k^4}=\frac{n}{24} t(4,n)=\frac{1}{24}\left(H_n^4+6H_n^2H_n^{(2)}+8H_nH_n^{(3)}+3(H_n^{(2)})^2+6H_n^{(4)}\right)$$

• Kink's property Commented Jan 29, 2023 at 20:04
• I generalized it .. hope you find it helpful Commented Jan 29, 2023 at 20:34

Let $$n\geq 1$$ and define the sequence, $$a_n = \sum_{k=1}^n {n\choose k} \frac{1}{k} (-1)^{k+1} = \sum_{k=1}^{\infty} {n\choose k} \frac{1}{k} (-1)^{k+1}$$ (If $$k>n$$ then the binomial coefficient is zero, not changing the sum).

The generating function of this sequence is equal to, $$A(x) = \sum_{n=1}^{\infty} a_n x^n = \sum_{n=1}^{\infty} \sum_{k=1}^{\infty} {n\choose k} \frac{1}{k} (-1)^{k+1} x^n = \sum_{k=1}^{\infty} \frac{(-1)^{k+1}}{k} \left\{ \sum_{n=1}^{\infty} {n\choose k} x^n \right\}$$ The series in the bracket is a variant of the geometric series and is well-known to sum to, $$A(x) = \sum_{k=1}^{\infty} \frac{(-1)^{k+1}}{k} \left\{ \frac{x^k}{(1-x)^{k+1}} \right\} = \frac{1}{1-x}\sum_{k=1}^{\infty} \frac{(-1)^{k+1}}{k} \left( \frac{x}{1-x} \right)^k$$ The remaining series is again well-known to sum of the logarithmic series, therefore, $$A(x) = \frac{1}{1-x} \log \left( 1 + \frac{x}{1-x} \right) = \frac{1}{1-x} \log \left( \frac{1}{1-x} \right)$$ Now recall that $$\log(\tfrac{1}{\theta}) = -\log(\theta)$$, therefore, by using logarithmic series again, $$A(x) = \frac{1}{1-x} \bigg( -\log(1-x) \bigg) = \frac{1}{1-x}\left( \sum_{k=1}^{\infty} \frac{x^k}{k} \right) = \left( \sum_{k=0}^{\infty} x^k \right) \left( \sum_{k=1}^{\infty} \frac{x^k}{k} \right)$$ Now it is easy to find the $$x^n$$ coefficient of $$A(x)$$, it is equal to, $$a_n = \frac{1}{n} + \frac{1}{n-1} + ... + \frac{1}{1} = \sum_{k=1}^n \frac{1}{k}$$

• Nice, variant of geometric series. Commented Jan 12, 2023 at 21:01

I didn't see the Newton series (sometimes called Stern series) of Digamma function: $$\psi(s+1)=-\gamma+\sum_{k=1}^{\infty}{s\choose k}\frac{(-1)^k}{k}\tag{1}$$ and we also have $$\psi(s+1)=-\gamma+\sum_{k=1}^{\infty} \frac{1}{k}-\frac{1}{s+k}\tag{2}$$ Let $$s=n$$ and the result follows by rearrangment of the second series.