# Combinatorics problem help

1. Jun 29, 2011

### Mentallic

1. The problem statement, all variables and given/known data
I need to show that $${^{2n}}C_n$$ is an even number.

2. Relevant equations
$${^n}C_k=\frac{n!}{k!(n-k)!}$$

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

2. Jun 29, 2011

### Bohrok

Re: Combinatorics

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

3. Jun 29, 2011

### SammyS

Staff Emeritus
Re: Combinatorics

Have you tried proof by induction?

4. Jun 29, 2011

### ehild

Re: Combinatorics

Think of Pascal's Triangle.

ehild

5. Jun 29, 2011

### Mentallic

Re: Combinatorics

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.

I'll give it a go.

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.

6. Jun 30, 2011

### spamiam

Re: Combinatorics

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!

7. Jun 30, 2011

### ehild

Re: Combinatorics

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

ehild

8. Jun 30, 2011

### Mentallic

Re: Combinatorics

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.

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.

9. Jun 30, 2011

### ehild

Re: Combinatorics

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

#### Attached Files:

• ###### pascal.JPG
File size:
4.6 KB
Views:
74
10. Jun 30, 2011

### I like Serena

Re: Combinatorics

Hi Mentallic!

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

11. Jun 30, 2011

### Mentallic

Re: Combinatorics

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

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.

12. Jun 30, 2011

### ehild

Re: Combinatorics

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

ehild

13. Jun 30, 2011

### I like Serena

Re: Combinatorics

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. :tongue2:

14. Jun 30, 2011

### Mentallic

Re: Combinatorics

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

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

15. Jun 30, 2011

### Gib Z

Re: Combinatorics

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

16. Jun 30, 2011

### I like Serena

Re: Combinatorics

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

17. Jun 30, 2011

### vela

Staff Emeritus
Re: Combinatorics

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

18. Jul 7, 2011

### mgill

Re: Combinatorics

wow genius solution!