MHB Can the Combinatorial Fun Formula Be Proven Using Induction?

[MarkFL]

Show that:

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

Hint:

Spoiler

Use:

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

for an appropriate value of $x$.

 

[Sudharaka]

Show that:

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

Hint:

Spoiler

Use:

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

for an appropriate value of $x$.

Hi everyone, :)

Spoiler

\[(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)\]

 

[Albert1]

in fact this also can be done using induction method

if you are interested ,I will do it later

 

[PaulRS]

Spoiler

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]

I want to thank everyone that participated. (Yes)

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

Spoiler

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

$$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 $${n+1 \choose 0}=1$$ and $${n+1 \choose r}=\frac{n+1}{r}\cdot{n \choose r-1}$$ to write:

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

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

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

 

[Albert1]

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 !