# Homework Help: Proof by induction

1. Oct 18, 2015

### gruba

1. The problem statement, all variables and given/known data
Prove that $\forall n\in \mathbb{N}$
$$\sum\limits_{k=1}^{n}(-1)^{k+1}{n\choose k}\frac{1}{k}=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}$$

2. Relevant equations
-Induction
-Summation
-Binomial coefficient

3. The attempt at a solution

For $n=1$ equality is true.

For $n=m$

$m-{m\choose 2}\frac{1}{2}+...+(-1)^{m+1}\frac{1}{m}=1+\frac{1}{2}+...+\frac{1}{m}$

For $n=m+1$

$\left(\sum\limits_{k=1}^{m}(-1)^{k+1}{m\choose k}\frac{1}{k}\right)+(-1)^{m+2}\frac{1}{m+1}=1+\frac{1}{2}+...+\frac{1}{m+1}$

If $m$ is even, equality is true, but not if $m$ is odd.
Is this correct?

Could someone explain this in detail?

2. Oct 18, 2015

### Buzz Bloom

Hi gruba:

(1) The series being added does not include (-1)k+1. That series should be 1-1/2+1/3-1/4...

(2) The series being added does not include (m over k) with each of the fractions.

Hint: For (m over k) see: https://en.wikipedia.org/wiki/Combination

I hope this helps.

Regards,
Buzz

3. Oct 18, 2015

### gruba

Are you sure it is a mistake?
I have some solution which I don't inderstand:

$\sum_{k=1}^{n}\binom{n}{k}(-1)^{k+1} x^k = 1-(1-x)^n\tag{1}$
$\sum_{k=1}^{n}\binom{n}{k}(-1)^{k+1}\frac{1}{k} = \int_{0}^{1}\frac{1-(1-x)^n}{x}\,dx= \int_{0}^{1}\frac{1-x^n}{1-x}\,dx\tag{2}$
$\sum_{k=1}^{n}\binom{n}{k}(-1)^{k+1}\frac{1}{k} = \int_{0}^{1}\left(1+x+\ldots+x^{n-1}\right)\,dx = 1+\frac{1}{2}+\ldots+\frac{1}{n}=H_n\tag{3}$

4. Oct 18, 2015

### Buzz Bloom

Hi gruba:

The left hand equality in your (2) is OK. I don't see how you get the right hand equality in your (2).

Ah. You substituted x -> (1-x). You forgot to also substitute dx -> -dx.

Regards,
Buzz

5. Oct 18, 2015

### gruba

This is my book's solution which I don't understand.
Is there some approach which doesn't involve integration?

6. Oct 18, 2015

### Buzz Bloom

Hi gruba:

I edited a bit more to my last post after you responded. Please take another look at my previous post.

Regards,
Buzz

7. Oct 18, 2015

### Buzz Bloom

Hi gruba:

Sorry. My mistake. The missing minus sign is corrected by reversing the top and bottom limits of the integration.

Regards,
Buzz

8. Oct 18, 2015

### Buzz Bloom

Hi gruba:

My apologies for my earlier confusion.

The derivation (1), (2) and (3) is a proof of the original equality. However it is not a proof by induction.

Going back to your original post, after
the (m over k) in the summation should be (m+1 over k).

Regards,
Buzz