Welcome to our community

Be a part of something great, join today!

Combinatorial fun!

  • Thread starter
  • Admin
  • #1

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
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
Feb 5, 2012
1,621
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
Jan 25, 2013
1,225
in fact this also can be done using induction method

if you are interested ,I will do it later
 

PaulRS

Member
Jan 26, 2012
37
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}\]
 
  • Thread starter
  • Admin
  • #5

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
I want to thank everyone that participated. (Yes)

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
Jan 25, 2013
1,225
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: