Proving the Identity using Binomial Theorem

[indigojoker]

I am asked to prove that \sum ^n _{k=0} (C^n_k)^2 = C^{2 n}_n

Where C^n_k signifies "n choose k"

I am told the hint to use the binomial theorem and to calculate the coefficient of x^n in the product (1+x)^n (1+x)^n = (1+x)^{2n}

the Binomial theorem is given by (x+y)^n = \sum_{k=0} ^n C_k^n x^{n-k} y^k

Following the hint, we see that:

(1+x)^n = \sum^n _{k=0} C^n _k x^{n-k}

(1+x)^{2n} = \sum^{2n} _{k=0} C^{2n} _k x^{2n-k}

I believe from here, I would like to show that:

\left( \sum^n _{k=0} C^n _k x^{n-k} \right) \left( \sum^n _{k=0} C^n _k x^{n-k} \right) = \sum^{2n} _{k=0} C^{2n} _k x^{2n-k}

And ultimately, I believe the goal is to get \sum ^n _{k=0} (C^n_k)^2 = C^{2 n}_n from the above relation but I'm not sure where to go from here.

Any ideas?

 

[Dick]

You can also write that as:
<br /> \left( \sum^n _{k=0} C^n _k x^{n-k} \right) \left( \sum^n _{j=0} C^n _j x^{j} \right) = \sum^{2n} _{k=0} C^{2n} _k x^{2n-k}<br />
The terms that produce a x^n on the left are the ones where k=j, yes? Write it as a single sum. Now look for the x^n on the right. Two polynomials can only be equal if the coefficients of each power of x are the same.

 

[indigojoker]

I'm still confused as to what was written.

I believe you meant to write:
<br /> <br /> \left( \sum^n _{k=0} C^n _k x^{n-k} \right) \left( \sum^n _{j=0} C^n _j x^{n-j} \right) = \sum^{2n} _{k=0} C^{2n} _k x^{2n-k}<br />

I'm not sure what "The terms that produce a x^n" exactly means, which is why I don't understand the restriction k=j.

Are you saying:

<br /> <br /> \sum^n _{k=0} C^n _k x^{n-k} C^n _k x^{n-k} = \sum^{2n} _{k=0} C^{2n} _k x^{2n-k}<br />

? I am not sure I follow, could you please explain?

 

[gabbagabbahey]

Using the binomial theorem,

(x+y)^n = \sum_{k=0} ^n C_k^n x^{n-k} y^k

you can write (1+x)^n in two different ways:

(1)Setting x\to x and y\to 1 you get

(1+x)^n = \sum^n _{k=0} C^n _k x^{n-k}

(2)Setting x\to 1 and y\to x you get

(1+x)^n = \sum^n _{k=0} C^n _k x^{k}=\sum^n _{j=0} C^n _j x^{j}

That means you can write:

(1+x)^n(1+x)^n=\left( \sum^n _{k=0} C^n _k x^{n-k} \right) \left( \sum^n _{j=0} C^n _j x^{j} \right)

And so, the expression Dick gave is perfectly valid.

Since the two summations on the LHS of that expression are over different indices, you can rewrite the product as:

\left( \sum^n _{k=0} C^n _k x^{n-k} \right) \left( \sum^n _{j=0} C^n _j x^{j} \right)= \sum^n _{j,k=0} (C^n _k x^{n-k})(C^n _j x^{j})

 

[indigojoker]

Ah, I see the step that was skipped. Thanks for clarification.

\sum^n _{j,k=0} (C^n _k x^{n-k})(C^n _j x^{j}) = \sum^{2n} _{k=0} C^{2n} _k x^{2n-k}

We want the coefficient of each power to be the same since the polynomials are the same...

However, x^{n-k} x^{j} and x^{2n-k} do not match, I'm trying to think of a way but I am not good with the various indices, is there a way to combine j and k? Since we are using one summation, why not just make j=k and have one summation?

 

[Dick]

Not every term can give an x^n. The power in the terms on the left is x^(n-k+j). That's equal to x^n only if k=j.

 

[indigojoker]

But how does that help match the right hand side of x^{2n-k}?

 

[Dick]

The only term in the sum on the right that is x^n is the one where k=n.

 

[indigojoker]

<br /> \sum^n _{j,k=0} (C^n _k x^{n-k})(C^n _j x^{j}) = \sum^{2n} _{k=0} C^{2n} _k x^{2n-k}

LHS: let j=k
RHS: let k=n

<br /> \sum^n _{k=0} (C^n _k C^n _k x^{n}) = \sum^{2n} _{n=0} C^{2n} _n x^{n}

for the polynomials to be equal, we must have the same coefficients, so can we say that:

since \sum_{n=0} ^{2n} =1 because n=0 then

<br /> x^n \sum^n _{k=0} (C^n _k C^n _k ) = x^n C^{2n} _n

on LHS we can bring the x^n out because it doesn't depend on k

<br /> \sum^n _{k=0} (C^n _k C^n _k ) = C^{2n} _n

is this a proper conclusion?

 

[Dick]

<br /> <br /> \sum^n _{k=0} (C^n _k C^n _k x^{n}) = \sum^{2n} _{n=0} C^{2n} _n x^{n} <br />

There is no summation on the right side. You want to pick out the only term that contains x^n. So,

<br /> <br /> \sum^n _{k=0} (C^n _k C^n _k x^{n}) = C^{2n} _n x^{n} <br />

There's not much need to argue after that.

 

[indigojoker]

Why is there no summation on the right side? Is it because n=0?

 

[gabbagabbahey]

Why is there no summation on the right side? Is it because n=0?

It's because you've picked out a single term in the series; the one that is of order x^n. That corresponds to the k=n term. You are not looking at the other 2n-1 terms where k≠n.

Likewise on the LHS; you are only looking at the terms that is of order x^n. That corresponds to the j=k term, so in the summation over j, you look only at the term where j=k.