Proving Equality Between Sequences Using Induction

[nuuskur]

Homework Statement

Show that $$\sum_{k=1}^n \frac{(-1)^{k-1}}{k} \binom{n}{k} = 1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n-1} + \frac{1}{n} = \sum_{k=1}^n \frac{1}{k}$$

Homework Equations

The Attempt at a Solution

Writing out few of the summands:
$$\frac{n!}{1\cdot 1!(n-1)!} - \frac{n!}{2\cdot 2!(n-2)!} + \frac{n!}{3\cdot 3!(n-3)!} - \frac{n!}{4\cdot 4!(n-4)!} +...\\<br /> n!(\frac{1}{1\cdot 1!(n-1)!}-\frac{1}{2\cdot 2!(n-2)!}+\frac{1}{3\cdot 3!(n-3)!}-\frac{1}{4\cdot 4!(n-4)!} + ...)$$
if this really adds up the way it's going to, I would somehow have to show that what is between the parenthesis adds up to $\frac{1}{k\cdot n!}$then $n!\cdot \frac{1}{k\cdot n!}$ would be 1/k: what I am looking for.
How should I proceed?

 

[mfb]

There is the related formula
$$\sum_{k=0}^n \frac{(-1)^{k}}{k} \binom{n}{k} = \begin{cases}
\frac{1}{n}, & \text{n odd}\\
1-\frac{1}{n},& \text{n even} \end{cases}$$
I wonder if you could prove both via induction (that's how I got that formula, using the result you want to show).