[SOLVED] Prove the following combinatorial identity?

**fardeen_gen** · February 9th 2009, 10:38 AM

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)

**Opalg** · February 9th 2009, 01:19 PM

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$ .

**fardeen_gen** · February 13th 2009, 04:49 AM

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

**Opalg** · February 13th 2009, 05:14 AM

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}$ .

**fardeen_gen** · February 13th 2009, 06:06 AM

What is (n - 1)Cn?

**Opalg** · February 13th 2009, 06:56 AM

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$ .

Thread: [SOLVED] Prove the following combinatorial identity?

LinkBack

Thread Tools

Display

[SOLVED] Prove the following combinatorial identity?

Similar Math Help Forum Discussions

Prove the identity using a combinatorial proof

Combinatorial proof for an identity

combinatorial identity problem

(Basic) Combinatorial Identity.

[SOLVED] Prove the identity, Stuck?

Search Tags