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:
$$\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}$$
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 /> \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}$$

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 /> \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}$$

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

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

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

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

$$\sum^n _{k=0} (C^n _k C^n _k ) = C^{2n} _n$$

is this a proper conclusion?

 

[Dick]

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

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

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

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.