Proving the Evenness of {^{2n}}C_n: A Combinatorics Challenge

[Mentallic]

Homework Statement

I need to show that $${^{2n}}C_n$$ is an even number.

Homework Equations

$${^n}C_k=\frac{n!}{k!(n-k)!}$$

The Attempt at a Solution

It was simple to convert the expression into factorials, but from there I really am stuck.

$$\frac{(2n)!}{(n!)^2}=\frac{2n(2n-1)(2n-2)...(n+2)(n+1)}{n(n-1)(n-2)...2\cdot1}$$

To show that it is even I would need to somehow cancel out the denominator, but I have had no such luck in doing so.

 

[Bohrok]

You have a 2 at the beginning of the expanded expression of (2n)!/(n!)²; won't that be enough to show that it's even?

 

[SammyS]

Have you tried proof by induction?

 

[ehild]

Think of Pascal's Triangle.

ehild

 

[Mentallic]

You have a 2 at the beginning of the expanded expression of (2n)!/(n!)²; won't that be enough to show that it's even?

No, because we need to show that the rest of the expression is an integer, and we haven't done so due to the fraction involved.

Have you tried proof by induction?

I'll give it a go.

Think of Pascal's Triangle.

ehild

Yes I was thinking maybe rather than algebraic manipulations, this question just needs a good old logical explanation as to why it must be true.

I'll get back to editing this when I've tried more things out.

 

[spamiam]

Think of Pascal's Triangle.

ehild

Wow, with those 4 words of advice, I solved this in about a minute!

For another hint, Mentallic, remember the properties
$$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$
and
$$\binom{n}{k} = \binom{n}{n-k}.$$

It should fall right out!

 

[ehild]

Wow, with those 4 words of advice, I solved this in about a minute!

But it took me about half an hour to find these four words.

ehild

 

[Mentallic]

Wow, with those 4 words of advice, I solved this in about a minute!

For another hint, Mentallic, remember the properties
$$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$
and
$$\binom{n}{k} = \binom{n}{n-k}.$$

Oh wow I wish I remembered the first equality. For a question in an exam that doesn't provide us with something like "use the equality ..." but it instead prefers to tell me that tan=sin/cos, I feel like I just got slapped in the face.

$$\binom{2n}{n}=\binom{2n-1}{n}+\binom{2n-1}{n-1}$$

$$\binom{2n-1}{n-1}=\binom{2n-1}{2n-1-(n-1)}=\binom{2n-1}{n}$$

Therefore

$$\binom{2n}{n}=2\binom{2n-1}{n}$$

But all valid binomials are integers, thus it is even.

But it took me about half an hour to find these four words.

ehild

Some wise words indeed


As for the proof by induction, I had some trouble along the way, and I'm unsure of what 'excuse' to use.

Assume $$\binom{2n}{n}=2a, a\in Z$$

and now prove $$\binom{2n+2}{n+1}=2b, b\in Z$$

$$\binom{2n+2}{n+1}=\frac{(2n+2)(2n+1)(2n)!}{(n+1)n!(n+1)n!}$$
$$=\frac{(2n+2)(2n+1)}{(n+1)^2}\binom{2n}{n}$$

Now all I can say at this point is that $$\binom{2n}{n}$$ is some integer, so I need to show that $$\frac{(2n+2)(2n+1)}{(n+1)^2}$$ is even for all integers n.

$$\frac{(2n+2)(2n+1)}{(n+1)^2}=2\left(\frac{2n+1}{n+1}\right)$$

And from this point I'm unsure, but I was also able to convert it into the form

$$=2\left(2-\frac{1}{n+1}\right)$$ and from this expression, it's quite clear that it is going to not be true, so I must have done something wrong.

 

[ehild]

You know that an element in the Pascal triangle is the sum of the two elements above it. And the triangle is symmetric.
The 2N line has odd number of elements, and that in question is just in the middle so the two other elements above it are equal.

ehild

 

[I like Serena]

Hi Mentallic!

Aren't you forgetting your induction assumption?
That is:
$$\binom{2n}{n}=2a, a\in Z$$
which is even?

 

[Mentallic]

You know that an element in the Pascal triangle is the sum of the two elements above it. And the triangle is symmetric.
The 2N line has odd number of elements, and that in question is just in the middle so the two other elements above it are equal.

ehild

That route would seem like such an easy way out, I would need to prove that both numbers above it are equal, no?

Hi Mentallic!

Aren't you forgetting your induction assumption?
That is:
$$\binom{2n}{n}=2a, a\in Z$$
which is even?

Oh, right It doesn't really change anything though, because I still need to show that the other factor is an integer and it clearly isn't. It's obvious that I went wrong somewhere along the way, yet I can't see where.

 

[ehild]

That route would seem like such an easy way out, I would need to prove that both numbers above it are equal, no?

Those two elements above are ^2n-1C_n-1 and ^2n-1C_n, are not they? Are not they the same? (Anyway, the Pascal triangle is symmetric.)

ehild

 

[I like Serena]

Oh, right It doesn't really change anything though, because I still need to show that the other factor is an integer and it clearly isn't. It's obvious that I went wrong somewhere along the way, yet I can't see where.

I checked your formula which is correct, so you didn't go wrong along the way.
However, you're left with proving that (n+1) divides $\binom{2n}{n}$, which is not immediately obvious. You can probably do it with full induction.

 

[Mentallic]

Those two elements above are ^2n-1C_n-1 and ^2n-1C_n, are not they? Are not they the same? (Anyway, the Pascal triangle is symmetric.)

ehild

Oh yes of course, and the fact that Pascal's triangle is symmetrical is nailed down once more
By they way, are they not?

I checked your formula which is correct, so you didn't go wrong along the way.
However, you're left with proving that (n+1) divides $\binom{2n}{n}$, which is not immediately obvious. You can probably do it with full induction.

If I were to expand the binomial, where exactly would I be using my inductive hypothesis?

 

[Gib Z]

For every way to choose n objects from 2n, there exists a complementary choice (the other n objects).

 

[I like Serena]

If I were to expand the binomial, where exactly would I be using my inductive hypothesis?

Dunno. I tried it for a little while, but I don't see yet how to do this with full induction. :(

 

[vela]

It was simple to convert the expression into factorials, but from there I really am stuck.

$$\frac{(2n)!}{(n!)^2}=\frac{2n(2n-1)(2n-2)...(n+2)(n+1)}{n(n-1)(n-2)...2\cdot1}$$

You simplified it too much. Try writing it like
$$\begin{pmatrix}2n \\ n\end{pmatrix} = \frac{2n!}{n! n!} = \frac{2n (2n-1)!}{n(n-1)! n!}=\cdots$$

 

[mgill]

For every way to choose n objects from 2n, there exists a complementary choice (the other n objects).

wow genius solution!