Proving the Summation Problem using Combinations

[MathematicalPhysicist]

i have to prove that:

n
sum [C(n,k)]^2=C(2n,n)
k=0
i have in my text a hint that i need to use:

(1+x)^n(1+x)^n=(1+x)^2n
but i got that:

n 2n
sum [C(n,k)]^2= sum [C(2n,k)]
k=0 k=0

how do i get out of this mess?

 

[MathematicalPhysicist]

it should be
2n
sum C(2n,n)
k=0

but i reackon you understood me the first time.

 

[HallsofIvy]

Of course, you know that $(1+ x)^n= \sum_{i=0}^n _nC_i x^i$ (the binomial theorem). What are the coefficients of (1+x)ⁿ(1+x)ⁿ in terms of _nC_i?

 

[MathematicalPhysicist]

2n_C_i

but still it the summation sign stays, unless i open it this way:

2n_C_1+2n_C_2+...+2n_C_2n
am i wrong here completely?

 

[HallsofIvy]

Notice that you are multiplying two sums together.
(a+ bx+ cx²)(u+ vx+ wx²)= au+ avx+ awx²+ bux+ bvx²+ bwx³+ cux²+ cvx³+ cwx⁴= au+ (av+bu)x+ (aw+ bv+ cu)x²+ (bw+ cv)x³+ cwx⁴.

Each coefficient is a sum.

 

[MathematicalPhysicist]

but here we have (1+2x+x^2)^n=(1+(2x+x^2))^n=
n
=sum n_C_k (2x+x^2)^k
k=0

when x=1

n
sum (n_C_k)*3^k= (n_C_0)+3*(n_C_1)+...+3^n
k=0

now how do i get from this, the final answer:
2n_C_n
?

 

[matt grime]

$$\binom{2n}{n}$$

is the coefficient of x^n in the expansion of (1+x)^{2n}

that is all the hint you need (oh, and to possibly forget what you'd done and start again).

 

[AKG]

Are you allowed to give arguments about how the left side represents the number of ways to make some choice, and show tha the right side represents the same thing, thereby proving that both quantities are equal? The number of ways to choose n objects from a set of 2n is equal to the number of ways to:

choose 0 from the first n AND then n from the second n
OR
choose 1 from the first n AND then n-1 from the second n
OR
.
.
.
OR
choose k from the first n AND n-k from the second n
OR
.
.
.
OR
choose n from the first n AND choose 0 from the second n

=

choose 0 from the first n AND then 0 from the second n
OR
choose 1 from the first n AND then 1 from the second n
OR
.
.
.
OR
choose k from the first n AND k from the second n
OR
.
.
.
OR
choose n from the first n AND choose n from the second n

since the number of ways to choose n-k elements from n is the same as the number of ways to choose k.

 

[MathematicalPhysicist]

$$\binom{2n}{n}$$

is the coefficient of x^n in the expansion of (1+x)^{2n}

that is all the hint you need (oh, and to possibly forget what you'd done and start again).

i know that
2n
(1+x)^2n=sum (2n_C_k)x^k
k=0

but how do i get the coeffient only, that's my big q?

 

[matt grime]

what does 'get the coefficient' mean?

Write down the expression in two different ways, equate coefficients.

EXAMPLE.

(1+x)^4 = 1+4x+10x^2+4x^3+x^4 here are the 4Cr

it also equals ((1+x)^2)^2=(1+x+x^2)^2=(2C0+2C1x + 2C0x^2)^2

now can you see how to find the coeffiecients in two different ways?

 

[benorin]

$$(1+x)^n=\sum_{k=0}^{n} _nC_kx^k$$ and $$(1+x)^{2n}=\sum_{k=0}^{2n} _{2n}C_kx^k$$

and since $$(1+x)^n(1+x)^n=(1+x)^{2n}$$ we have

$$(1+x)^n(1+x)^n=\left( \sum_{k=0}^{n} _nC_kx^k\right) \left( \sum_{j=0}^{n} _nC_jx^j\right) = \sum_{k=0}^{2n} _{2n}C_kx^k = (1+x)^{2n}$$

from here, multiply out

$$\left( \sum_{k=0}^{n} _nC_kx^k\right) \left( \sum_{j=0}^{n} _nC_jx^j\right)$$

to get a sum of the form

$$\sum_{k=0}^{2n} a_kx^k$$

where you need to figure out what the a_k's are. It then follows that, equating coefficients of like powers of x, we must have

$$a_k= _{2n}C_k$$.

 

[MathematicalPhysicist]

what does 'get the coefficient' mean?

Write down the expression in two different ways, equate coefficients.

EXAMPLE.

(1+x)^4 = 1+4x+10x^2+4x^3+x^4 here are the 4Cr

it also equals ((1+x)^2)^2=(1+x+x^2)^2=(2C0+2C1x + 2C0x^2)^2

now can you see how to find the coeffiecients in two different ways?

now i get it.
it took time, but thanks matt and halls, and also the new guy, benorin.
(-: