I have to prove the following $$\sum_{k=1}^n \frac{(-1)^{k-1}}{k} {n \choose k} =1+\frac{1}{2}+...+\frac{1}{n}$$ I try to prove it using that $$\sum_{k=0}^n {(-1)^{n-k}} {n \choose k} k^m = \begin{cases} 0, & \text{if $m<n$ } \\ n!, & \text{if $m=n$ } \end{cases} $$ but my biggest problem is $ (-1)^{n-k} $
Any thoughts on that or another way to approach this?
On
An overkill. By the Melzak's identity with $f\equiv1$ we have $$\sum_{k=1}^{n}\dbinom{n}{k}\frac{\left(-1\right)^{k-1}}{x+k}=\frac{1}{x}-\frac{1}{x\dbinom{x+n}{n}}=\frac{\dbinom{x+n}{n}-1}{x\dbinom{x+n}{n}}$$ then taking $x\rightarrow0$ and recalling that $$\frac{d}{dx}\dbinom{x+n}{n}=\dbinom{x+n}{n}\left(\psi^{\left(0\right)}\left(n+x+1\right)-\psi^{\left(0\right)}\left(x+1\right)\right)$$ where $\psi^{\left(0\right)}\left(x\right)$ is the Digamma function, we have $$\sum_{k=1}^{n}\dbinom{n}{k}\frac{\left(-1\right)^{k-1}}{k}=\color{red}{\sum_{m=1}^{n}\frac{1}{m}}.$$
On
Following the comment of @MehrdadZandigohar ...
Consider for $n=1,2,\ldots$ \begin{align*} \color{blue}{f_n}&\color{blue}{=\sum_{k=1}^n(-1)^{k-1}\binom{n}{k}\frac{1}{k}}\\ &=\sum_{k=1}^n(-1)^{k-1}\left[\binom{n-1}{k}+\binom{n-1}{k-1}\right]\frac{1}{k}\tag{1}\\ &=f_{n-1}-\frac{1}{n}\sum_{k=1}^n(-1)^k\binom{n}{k}\tag{2}\\ &=f_{n-1}-\frac{1}{n}\left[(1-1)^n-1\right]\tag{3}\\ &=f_{n-1}+\frac{1}{n}\\ &\,\,\color{blue}{=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}} \end{align*} since $f_1=1$.
Comment:
In (1) we use the binomial identity $\binom{p}{q}=\binom{p-1}{q}+\binom{p-1}{q-1}$.
In (2) we split the sum and represent the resulting left-hand sum as $f_{n-1}$ and use for the right-hand sum the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.
In (3) we apply the binomial theorem.
$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{k = 1}^{n}{\pars{-1}^{k - 1} \over k}{n \choose k} & = \sum_{k = 1}^{n}\pars{-1}^{k - 1}{n \choose k}\int_{0}^{1}t^{k - 1}\,\dd t = -\int_{0}^{1}\sum_{k = 1}^{n}{n \choose k}\pars{-t}^{k}\,{\dd t \over t} \\[5mm] & = -\int_{0}^{1}{\pars{1 - t}^{n} - 1 \over t}\,\dd t = \int_{0}^{1}{t^{n} - 1 \over t - 1}\,\dd t = \int_{0}^{1}\sum_{k = 0}^{n - 1}t^{k}\,\dd t = \sum_{k = 0}^{n - 1}\int_{0}^{1}t^{k}\,\dd t \\[5mm] & = \sum_{k = 0}^{n - 1}{1 \over k + 1}\,\dd t = \sum_{k = 1}^{n}{1 \over k}\,\dd t = \bbx{1 + {1 \over 2} + \cdots + {1 \over n}} \end{align}