Combinatorial fun!

MarkFL

Administrator
Staff member
Show that:

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

Hint:

Use:

$$\displaystyle (1+x)^n=\sum_{k=0}^n\left({n \choose k}x^k \right)$$

for an appropriate value of $x$.

Sudharaka

Well-known member
MHB Math Helper
Show that:

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

Hint:

Use:

$$\displaystyle (1+x)^n=\sum_{k=0}^n\left({n \choose k}x^k \right)$$

for an appropriate value of $x$.
Hi everyone,

$(1+x)^n=\sum_{k=0}^n\left({n \choose k}x^k \right)$

$\Rightarrow\int_{0}^{x}(1+x)^n\, dx=\int_{0}^{x}\sum_{k=0}^n\left({n \choose k}x^k \right)\, dx$

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

Substitute $$x=-1$$ and we get,

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

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

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

Albert

Well-known member
in fact this also can be done using induction method

if you are interested ,I will do it later

PaulRS

Member
Note that (I changed the exponent of $-1$ from $k-1$ to $k+1$, but this leaves the result unchanged) :
$\sum_{k=1}^n \binom{n}{k} \cdot \tfrac{(-1)^{k+1}}{k+1} = \tfrac{1}{n+1}\cdot \sum_{k=1}^n \binom{n+1}{k+1} \cdot (-1)^{k+1}$

since $\binom{n}{k} \cdot \frac{n+1}{k+1} = \frac{n!}{k! \cdot (n-k)!} \cdot \frac{n+1}{k+1} = \frac{(n+1)!}{(k+1)! \cdot (n-k)!} = \frac{(n+1)!}{(k+1)! \cdot (n+1 - (k+1))!} = \binom{n+1}{k+1}$

And now we have, by the binomial theorem:
$\sum_{k=1}^n \binom{n+1}{k+1} \cdot (-1)^{k+1} = \sum_{k=2}^{n+1} \binom{n+1}{k} \cdot (-1)^{k} = (1-1)^{n+1} - \binom{n+1}{0} + \binom{n+1}{1} = n$

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

MarkFL

Administrator
Staff member
I want to thank everyone that participated.

Here is my solution (similar to that of PaulRS):

Begin with the binomial theorem as given with $x=-1$:

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

Use the identities $$\displaystyle {n+1 \choose 0}=1$$ and $$\displaystyle {n+1 \choose r}=\frac{n+1}{r}\cdot{n \choose r-1}$$ to write:

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

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

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

Albert

Well-known member
I will use the induction and the following formula :
$C_\left (n,k\right )=C_\left (n-1,k\right )+C_\left (n-1,k-1\right )$
n=1
$\dfrac{-1^0}{1+1}C_\left (1,1\right )=\dfrac {1}{1+1}=\dfrac{1}{2}$
n=2
$\dfrac{-1^0}{1+1}C_\left(2,1\right )+\dfrac{-1^1}{2+1}C_\left(2,2\right)=\dfrac{2}{3}$
$=\dfrac{1}{2}+\dfrac{1}{2\times 3}$
n=3
$\dfrac{1}{2}C_\left(3,1\right)-\dfrac{1}{3} C_\left(3,2\right)+\dfrac{1}{4}C_\left(3,3\right)=\dfrac{3}{4}$
$=\dfrac{2}{3}+\dfrac{1}{3\times 4}$
-------
-------
suppose n=n-1
$\dfrac{1}{2}C_\left (n-1,1\right)-\dfrac{1}{3}C_\left(n-1,2\right)+---+\dfrac{-1^{(n-2)}}{n}C_\left(n-1,n-1\right)=\dfrac{n-1}{n}$
$=\dfrac{n-2}{n-1}+\dfrac{1}{(n-1)\times n}$
n=n
$\dfrac{1}{2}C_\left (n,1\right)-\dfrac{1}{3}C_\left(n,2\right)+---+\dfrac{-1^{(n-1)}}{n+1}C_\left(n,n\right)=\dfrac{n}{n+1}$
$=\dfrac{n-1}{n}+\dfrac{1}{n\times (n+1)}$
so the proof is done !

Last edited: