# Thread: [SOLVED] Prove the following combinatorial identity?

1. ## [SOLVED] Prove the following combinatorial identity?

By expanding (x/(1 - x))^n , 0<x<1 , in 2 ways, prove that:

nC0(2n-1)Cn - nC1(2n - 2)Cn + nC2(2n - 3)Cn - ... = 1

NOTE: nC0 represents n choose 0.
nC0(2n-1)Cn represents (n choose 0) multiplied by (2n - 1 choose n)

2. Originally Posted by fardeen_gen
By expanding (x/(1 - x))^n , 0<x<1 , in 2 ways, prove that:

nC0(2n-1)Cn - nC1(2n - 2)Cn + nC2(2n - 3)Cn - ... = 1

NOTE: nC0 represents n choose 0.
nC0(2n-1)Cn represents (n choose 0) multiplied by (2n - 1 choose n)
Use the binomial expansion $(1-x)^{-k} = 1 + kx + \tfrac{k(k+1)}{2!}x^2 + \tfrac{k(k+1)(k+2)}{3!}x^3 + \ldots = \sum_{j=0}^\infty{k+j-1\choose j}x^j$.

Then $\Bigl(\tfrac x{1-x}\Bigr)^n = x^n(1+nx+\ldots)$. But also $\tfrac x{1-x} = -\bigl(1-\tfrac1{1-x}\bigr)$, and so

\begin{aligned}\Bigl(\tfrac x{1-x}\Bigr)^n = (-1)^n\Bigl(1-\tfrac1{1-x}\Bigr)^n &= (-1)^n\sum_{k=0}^n{n\choose k}\Bigl(\tfrac{-1}{1-x}\Bigr)^k \\ &= (-1)^n\sum_{k=0}^n{n\choose k}(-1)^k\sum_{j=0}^\infty{k+j-1\choose j}x^j\end{aligned}
(using the above expansion for $(1-x)^{-k}$).

Now compare the coefficients of $x^n$ in the two expansions of $\Bigl(\tfrac x{1-x}\Bigr)^n$.

3. That gave me:
1 = nC0.(n-1)Cn - nC1.nCn + nC2.(n + 1)Cn + ...
Which is obviously wrong.
What am I missing?

4. Originally Posted by fardeen_gen
That gave me:
1 = nC0.(n-1)Cn - nC1.nCn + nC2.(n + 1)Cn + ...
Which is obviously wrong.
What am I missing?
It's not wrong. It's a finite series, which looks like
$1 = \textstyle(-1)^n\Bigl({n\choose0}{n-1\choose n} - {n\choose1}{n\choose n} + {n\choose2}{n+1\choose n} - \ldots + (-1)^{n-1}{n\choose n-1}{2n-2\choose n} + (-1)^n{n\choose n}{2n-1\choose n}\Bigr)$.
Now write the terms in reverse order, and use the fact that $\textstyle{n\choose k} = {n\choose n-k}$.

5. What is (n - 1)Cn?

6. Originally Posted by fardeen_gen
What is (n - 1)Cn?
I think you have to interpret that as 0. You can check that by tracing this term back to where it came from in the expansion of $\Bigl(\tfrac{-1}{1-x}\Bigr)^k$.