# Summation problem

1. Feb 6, 2006

### 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?

2. Feb 6, 2006

### MathematicalPhysicist

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

but i reackon you understood me the first time.

3. Feb 6, 2006

### HallsofIvy

Staff Emeritus
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)n(1+x)n in terms of nCi?

4. Feb 6, 2006

### 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?

5. Feb 6, 2006

### HallsofIvy

Staff Emeritus
Notice that you are multiplying two sums together.
(a+ bx+ cx2)(u+ vx+ wx2)= au+ avx+ awx2+ bux+ bvx2+ bwx3+ cux2+ cvx3+ cwx4= au+ (av+bu)x+ (aw+ bv+ cu)x2+ (bw+ cv)x3+ cwx4.

Each coefficient is a sum.

6. Feb 7, 2006

### 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
?

7. Feb 7, 2006

### 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).

8. Feb 7, 2006

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

9. Feb 8, 2006

### MathematicalPhysicist

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?

10. Feb 8, 2006

### 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?

11. Feb 8, 2006

### 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 ak's are. It then follows that, equating coefficients of like powers of x, we must have

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

12. Feb 8, 2006

### MathematicalPhysicist

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