Summing proof

Printable View

February 18th 2008, 03:48 AM
Deadstar

Summing proof

Let n be a nonnegative integer. Use the identity

${(1 + x)^n}{(1 + x)^n} = {(1 + x)^{2n}}$

To show that

$\sum_{k=0}^n {n \choose k}^2 = {2n \choose n}$ .

So far ive gotten to...

Using the binomial theorem;

$(x + y)^n = \sum_{k=0}^n {n \choose k} x^{n-k}y^k$ and setting x and y to one we get;

$(1 + x)^n = \sum_{k=0}^n {n \choose k}$

so...

$\sum_{k=0}^n {n \choose k}^2 = (1 + x)^n(1 + x)^n = (1 + x)^{2n}$ but from here i dont know what to do... Any help please?
February 18th 2008, 04:08 AM
topsquark

Quote:

Originally Posted by Deadstar

Let n be a nonnegative integer. Use the identity

${(1 + x)^n}{(1 + x)^n} = {(1 + x)^{2n}}$

To show that

$\sum_{k=0}^n {n \choose k}^2 = {2n \choose n}$ .

So far ive gotten to...

Using the binomial theorem;

$(x + y)^n = \sum_{k=0}^n {n \choose k} x^{n-k}y^k$ and setting x and y to one we get;

$(1 + x)^n = \sum_{k=0}^n {n \choose k}$

so...

$\sum_{k=0}^n {n \choose k}^2 = (1 + x)^n(1 + x)^n = (1 + x)^{2n}$ but from here i dont know what to do... Any help please?

I can't really help you, but you have two errors:
$(1 + x)^n = \sum_{k=0}^n {n \choose k}x^k$

And
$\sum_{k=0}^n \left ( {n \choose k} x^k \right )^2 \neq (1 + x)^n(1 + x)^n$

We can say that
$(1 + x)^n(1 + x)^n = \sum_{k = 0}^n \sum_{j = 0}^n {n \choose k}{n \choose j}x^kx^j$
but I don't see how this helps you.

-Dan
February 18th 2008, 04:20 AM
Deadstar

ok well how about

$\sum_{k=0}^n {n \choose k}^2 = (1 + 1)^n(1 + 1)^n = 2^{2n}$ where to now?
February 18th 2008, 04:24 AM
topsquark

Quote:

Originally Posted by Deadstar

ok well how about

$\sum_{k=0}^n {n \choose k}^2 = (1 + 1)^n(1 + 1)^n = 2^{2n}$ where to now?

This is what I'm trying to tell you
$\sum_{k=0}^n {n \choose k}^2 = (1 + 1)^n(1 + 1)^n \neq 2^{2n}$

Try it for n = 3 for example:
$\sum_{k=0}^n {n \choose k}^2 = 20$
not $2^{2 \cdot 3} = 2^6 = 64$

-Dan
February 18th 2008, 04:29 AM
Plato

Using Dan’s hint: $(1 + x)^n(1 + x)^n = \sum_{k = 0}^n \sum_{j = 0}^n {n \choose k}{n \choose j}x^kx^j$ let x=1.
Then $(2)^n(2)^n = \sum_{k = 0}^n \sum_{j = 0}^n {n \choose k}{n \choose j}$ and we know that $(2)^n = \sum_{k = 0}^n {n \choose k}$ .
Can you finish?