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

Question

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.

Thanks in advance.

Answer 1

Start with the generating function

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

Answer 2

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.

Answer 3

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.

Answer 4

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