1. ## Proving combinatoric identity

Hi,

I need to prove the following identity:

I thought it's somewhat similar to the Newton's binomial theorem, but I coudn't find how to solve this using this theorem.
Do you have an idea how can I solve this in any algebric/combinatoric way?

2. ## Re: Proving combinatoric identity

If you know the calculus, there's a simple proof of your formula. However, unfortunately, I couldn't find any purely algebraic proof.

For n any non-negative integer and x any real,
$$(1+x)^n=\sum_{i=0}^nC_i^nx^i$$
Now integrate each side of the above equation from 0 to 1; first the integral of the left side:
$$\int_0^1(1+x)^n\,dx={(1+1)^{n+1}\over n+1}-{(1+0)^{n+1}\over n+1}={2^{n+1}-1\over n+1}$$
Now the integral of the right side:
$$\sum_{i=0}^nC^n_i\int_0^1x^i\,dx=\sum_{i=0}^nC^n _i{1^{i+1}-0^{i+1}\over i+1}=\sum_{i=0}^n{C^n_i\over i+1}$$

3. ## Re: Proving combinatoric identity

$1+\sum _{k=0}^n \frac{n+1}{k+1}C_k^n=1+\sum _{k=0}^n C_{k+1}^{n+1}=$

$1+\sum _{k=1}^{n+1} C_k^{n+1}=\sum _{k=0}^{n+1} C_k^{n+1}=2^{n+1}$