# Thread: Proof Help

1. ## Proof Help

Prove that for all K > 0, (2k choose k) is an even number.

2. Originally Posted by jzellt
Prove that for all K > 0, (2k choose k) is an even number.

The sum of all the binomial coefficients (n choose j), as j goes from 0 to n, is 2^n, which is even. The coefficients pair off, with (n choose j) = (n choose n–j), and obviously the sum of each pair is even. If n=2k is even, there is a "left-over" term (2k choose k), in the middle of the sequence, which does not pair off with another term. In order for the sum of the whole sequence to be even, this term must clearly be even.

3. $\displaystyle {2k \choose k} = \frac{(2k)!}{k!(2k-k)!} = \frac{(2k)!}{(k!)^2}$.

For $\displaystyle k=1$ the assertion is true.

$\displaystyle (2k)! = 2 \cdot 3 \cdot \mathellipsis \cdot k \cdot (k+1) \mathellipsis 2k$ and $\displaystyle (k!)^2 = (2 \cdot 3 \cdot \mathellipsis \cdot k)(2 \cdot 3 \cdot \mathellipsis \cdot k)$

Cancelling where possible we have:

$\displaystyle \frac{(2k)!}{(k!)^2} = \frac{(k+1)(k+2) \mathellipsis 2k}{(2 \cdot 3 \cdot \mathellipsis \cdot k)}$.

Now the power of $\displaystyle 2$ in the prime factorization of $\displaystyle (k+1)(k+2) \mathellipsis 2k$ is exactly $\displaystyle k$ (easy proof by induction). But the power of 2 in the prime factorization of $\displaystyle (2 \cdot 3 \cdot \mathellipsis \cdot k)$ is less than $\displaystyle k$ (another easy proof by induction) and therefore the quotient must be even.