1
$\begingroup$

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} $

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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}$ .

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

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?

$\endgroup$
  • $\begingroup$ Yes i do, even have it out right in front of me right now $\endgroup$ – user482578 Oct 23 '17 at 23:14
  • $\begingroup$ @A.Mercs I'm glad to hear it. Does this hint help? $\endgroup$ – Franklin Pezzuti Dyer Oct 23 '17 at 23:16
  • $\begingroup$ Yes, somewhat. I'm assuming I can make the substitution in the LHS using hint 1, right? $\endgroup$ – user482578 Oct 23 '17 at 23:17
  • 1
    $\begingroup$ Um... no. You should end up with $$\frac{1}{n+1}\sum_{k=0}^n \binom{n+1}{k+1}(-1)^{k+1}$$ $\endgroup$ – Franklin Pezzuti Dyer Oct 23 '17 at 23:26
  • 1
    $\begingroup$ 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}$ $\endgroup$ – user482578 Oct 23 '17 at 23:39

Your Answer

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