<s>[INST] 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.
Thanks in advance.
 [/INST] 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} $$
</s>