2
$\begingroup$

Find the value of $\sum_0^n \binom{n}{k} (-1)^k \frac{1}{k+1}$.

Writing out several terms, I think the answer is $1/(n+1)$, but I'm struggling to prove this. I would greatly appreciate it if someone could show how to prove this.

$\endgroup$
1
  • $\begingroup$ Show your work. $\endgroup$
    – Empty
    Oct 21 '15 at 11:46
4
$\begingroup$

Hint: $${n\choose k}\frac{1}{k+1} = \frac{1}{n+1}\frac{(n+1)!}{(k+1)! (n+1-(k+1))!}=\frac{1}{n+1}{n+1\choose k+1}.$$

$\endgroup$
2
$\begingroup$

Here’s a combinatorial argument. I have $n$ students numbered $1$ through $n$ and a teacher, and I want to count the ways in which these $n+1$ people can line up with the teacher at the front of the line. Of course this is just $n!$. However, I can also calculate it by an inclusion-exclusion argument. Let $A_i$ be the set of permutations in which student $i$ is in front of the teacher. If $1\le k\le n$, and $F\subseteq[n]$ has cardinality $k$, then

$$\left|\bigcap_{i\in F}A_i\right|=\frac{(n+1)!}{k+1}\;.$$

There are $\binom{n}k$ such subsets $F$, so the number of permutations with the teacher at the front is

$$\begin{align*} (n+1)!-\left|\bigcup_{i\in[n]}A_i\right|&=(n+1)!-\sum_{k=1}^n\binom{n}k(-1)^{k-1}\frac{(n+1)!}{k+1}\\ &=(n+1)!\sum_{k=0}^n\binom{n}k(-1)^k\frac1{k+1}\;. \end{align*}$$

Thus,

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

$\endgroup$
1
$\begingroup$

Use the well known binomial expansion

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

Integrate the above expression from $x=0$ to $x=1$. The expected result follows.

$\endgroup$

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