# How to prove combinatoric identity

How would you prove this identity using combinatorics? Any hints or advice?

For all positive integers $n>1$,

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

We obtain \begin{align*} \color{blue}{\sum_{k=0}^n\frac{1}{k+1}\binom{n}{k}(-1)^{k+1}} &=\frac{1}{n+1}\sum_{k=0}^n\binom{n+1}{k+1}(-1)^{k+1}\tag{1}\\ &=\frac{1}{n+1}\sum_{k=1}^{n+1}\binom{n+1}{k}(-1)^{k}\tag{2}\\ &=\frac{1}{n+1}(1-1)^{n+1}-\frac{1}{n+1}\tag{3}\\ &\color{blue}{=-\frac{1}{n+1}} \end{align*}

Comment:

• In (1) we use the binomial identity $\binom{n+1}{k+1}=\frac{n+1}{k+1}\binom{n}{k}$.

• In (2) we shift the index to start from $k=1$.

• In (3) we apply the binomial summation formula and subtract $\frac{1}{n+1}$ as compensation for the lower limit starting with $1$ instead of $0$.

We have: $f(x) = \dfrac{1}{k+1}\cdot \displaystyle \sum_{k=0}^n \binom{n}{k}x^{k+1}\implies f'(x) = (1+x)^n\implies f(x) = f(0) + \displaystyle \int_{0}^x f'(t)dt = 0 + \displaystyle \int_{0}^x(1+t)^ndt = \displaystyle \int_{1}^{1+x}u^ndu= \dfrac{u^{n+1}}{n+1}|_{u=1}^{u=x+1}= \dfrac{(x+1)^{n+1}}{n+1}- \dfrac{1}{n+1}\implies f(-1) = -\dfrac{1}{n+1}$ .

• Integrals? Why?! – Franklin Pezzuti Dyer Oct 23 '17 at 23:31
• Just give it a different opinion to solve it. – DeepSea Oct 23 '17 at 23:35
• Interesting! (+1) :D – Franklin Pezzuti Dyer Oct 23 '17 at 23:37

HINT 1: Notice that $$\frac{1}{k+1}\binom{n}{k}=\frac{1}{n+1}\binom{n+1}{k+1}$$

HINT 2: Do you know the binomial theorem?

• Yes i do, even have it out right in front of me right now – user482578 Oct 23 '17 at 23:14
• @A.Mercs I'm glad to hear it. Does this hint help? – Franklin Pezzuti Dyer Oct 23 '17 at 23:16
• Yes, somewhat. I'm assuming I can make the substitution in the LHS using hint 1, right? – user482578 Oct 23 '17 at 23:17
• Um... no. You should end up with $$\frac{1}{n+1}\sum_{k=0}^n \binom{n+1}{k+1}(-1)^{k+1}$$ – Franklin Pezzuti Dyer Oct 23 '17 at 23:26
• So after fixing my blunder I have what you have but then you can take out a -1 which makes it $\frac{-1}{n+1}\sum_{k=0}^n \binom{n+1}{k+1}(-1)^{k}$ – user482578 Oct 23 '17 at 23:39