Proof the formula

Question

I have to prove the following formula:

$$\sum_{k=0}^n \frac{(-1)^k}{k+1} \binom{n}{k} = \frac{1}{n+1}$$

I do have absolutely no clue ye about how to even start. I'm thinking about using binomial theorem, but how?

Edit: Thanks to all the answers, but these are too complicated for me and use theorems which we do not use yet. Induction seem to be a way to go, but I'm constantly stuck there.

$$\sum_{k=0}^n \frac{(-1)^k}{k+1} \binom{n}{k} = \frac{1}{n+1}$$ n to n+1: $$\sum_{k=0}^{n+1} \frac{(-1)^k}{k+1} \binom{n+1}{k}$$ $$\sum_{k=0}^{n} (\frac{(-1)^k}{k+1} \binom{n+1}{k}) + \frac{(-1)^{n+1}}{(n+1)+1}$$

I'm probably missing something very basic there...

Answer 1

We have

$$\sum_{k=0}^n \frac{(-1)^k}{k+1} \binom{n}{k} =\sum_{k=0}^n (-1)^k\binom{n}{k}\int_0^1 x^kdx=\int_0^1 \sum_{k=0}^n (-x)^k\binom{n}{k}dx\\=\int_0^1(1-x)^n=\frac1{n+1}$$

Answer 2

Let $f(x) = -\sum_{k=0}^n \binom nk \frac{(-x)^{k+1}}{k+1}$. You look for $f(1)$, and $f(0) = 0$.

Then: \begin{align} f'(x) &= \sum_{k=0}^n \binom nk (-1)^{k} x^k = (1-x)^n \\\implies f(x) &= -\frac{(1-x)^{n+1}}{n+1} + \frac 1{n+1} \implies f(1) = \frac 1{n+1} \end{align}

Answer 3

Since $$\frac{1}{k+1}\binom{n}{k}=\frac{1}{n+1}\binom{n+1}{k+1}$$ we have: $$\sum_{k=0}^{n}\frac{(-1)^k}{k+1}\binom{n}{k}=\frac{1}{n+1}\sum_{k=0}^{n}\binom{n+1}{k+1}(-1)^k = \frac{1}{n+1}.$$

Answer 4

Hint: $$\sum_{k=0}^n {n \choose k} (-1)^{n-k} x^k = (x - 1)^n,$$

so $$\int_0^{1} \sum_{k=0}^n {n \choose k} (-1)^{n-k} x^k \,\, dx = \int_0^1 (x - 1)^n \,\, dx.$$

Answer 5

For $n=4$, observe$$(4+1)\left(\frac{\color{green}1}1-\frac{\color{green}4}2+\frac{\color{green}6}3-\frac{\color{green}4}4+\frac{\color{green}1}5\right)=\color{blue}5-\color{blue}{10}+\color{blue}{10}-\color{blue}5+\color{blue}1=1-(1-1)^5.$$ Then the sum is $$\frac1{4+1}=\frac1{n+1}.$$

It is no coincidence that the binomial numbers reappear, and the formula generalizes to all $n$: $$\frac {n^+}{k^+}\color{green}{\frac{n!}{k!(n-k)!}}=\color{blue}{\frac{n^+!}{k^+!(n^+-k^+)!}}.$$