7
$\begingroup$

I'm trying to prove that

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

So far I've tried induction (which doesn't really work at all), using well known facts such as

$$\sum_{k=0}^n {n \choose k} (-1)^k = 0$$

and trying to apply identities like

$${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$$

Would anyone be able to point me towards the right method? Should I be looking to apply an identity or is there a method I'm missing?

$\endgroup$
9
$\begingroup$
  • Note that $$(1-x)^{n} = \sum_{k=0}^{n} {n \choose k}(-1)^{n-k}\ x^{k} =(-1)^{n}\sum_{k=0}^{n}{n\choose k} (-1)^{-k}x^{k} =(-1)^{n}\sum_{k=0}^{n}{n\choose k} (-1)^{k}x^{k}$$ And since $\displaystyle \int_{0}^{1} x^{k} \ dx = \frac{1}{k+1}$. Its worth looking at $\displaystyle \int_{0}^{1} (1-x)^{n} \ dx$
$\endgroup$
  • $\begingroup$ This is a good hint, but shouldn't the expression for the sum be $$\binom{n}{k}(-1)^{n-k}x^k$$ or $$\binom{n}{k}(-1)^kx^{n-k}$$ right? $\endgroup$ – cjferes Oct 8 '14 at 15:28
  • 1
    $\begingroup$ @cjferes thanks. I have edited it. $\endgroup$ – crskhr Oct 8 '14 at 15:40
  • $\begingroup$ Note that $\sum_{k=0}^n {n \choose k} (-1)^k x^{k} = (1-x)^{n}$, then integral on $[0,1]$. $\endgroup$ – Alfred Chern Oct 9 '14 at 2:36
  • $\begingroup$ The expression for the sum should be ${n\choose k}(1)^{n-k}\ (-x)^{k}$but not ${n \choose k}(-1)^{n-k}\ x^{k}$ $\endgroup$ – Alfred Chern Oct 9 '14 at 2:40
3
$\begingroup$

From $(k+1)\binom{n+1}{k+1} = (n+1)\binom{n}{k}$ we get

\begin{align*} \sum_{k=0}^n \binom{n}{k} (-1)^k \frac{1}{k+1} &= \frac{1}{n+1} \sum_{k=0}^n \binom{n+1}{k+1}(-1)^k \\ &= \frac{1}{n+1} \Bigl( 1 + \sum_{r=0}^{n+1} \binom{n+1}{r} (-1)^{r-1} \Bigr) \\ &= \frac{1}{n+1} \end{align*} as required.

$\endgroup$
1
$\begingroup$

This is a special case ($x=1$) of the identity $$ \sum_{k=0}^n \binom{n}{k}\frac{(-1)^k}{k+x} = \frac{1}{x\binom{n+x}{n}} $$ which is proved in Concrete Mathematics, section 5.3, page 188. The outline of the proof is:

Show that the n-th difference of $1/x$ is $$ \frac{(-1)^n}{\binom{n+x}{n}} $$ This is easy using the methods of finite calculus, cf. chapter 2 of that same book; it is analogous to the n-th derivative of $1/x$.

And show that the n-th difference of any function $f(x)$ is given by $$ \Delta^n f(x) = \sum_k \binom{n}{k} (-1)^{n-k} f(x+k) $$

This can be proved by induction, but it also has a cute proof using the concept of the shift operator $E(f(x) = f(x+1)$ and writing $\Delta^n$ as $(E-1)^n$.

Then using $f(x)=1/x$ the result follows.

$\endgroup$
0
$\begingroup$

Try it as a Abel summation, i.e.

$$\sum f(k)\Delta g(k)\delta k=f(k)g(k)-\sum g(k+1)\Delta f(k)\delta k$$

where

$$\sum_{a}^{b}f(k)\delta k=\sum_{k=a}^{b-1}f(k)$$

For more information about finite calculus you can see by example here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.