# Prove that $2^n | P(2n, n)$

I am attempting to use Induction to prove this, but I am not sure if it is the right method to take. Here is what I have tried:

Induction Hypothesis: Assume $P(k)$ is true for some fixed $k \geq 1$ or $2^k | \frac {2k!}{2k-k!}$

Induction Step: Prove that $P(k+1)$ is true.

$$P(k+1)=P(2(k+1),k)= \frac{2(k+1)!}{(2(k+1)-k)!}$$

$$= \frac {2(k+1)k!}{2k+2-k)!}$$ $$= \frac {2(k+1)k!}{(k+2)!}$$

and this is where I am stuck, I know I can't distribute the factorials through. I am not even sure that this is the right approach. Any hints or tips would be greatly appreciated.

-
Don't conflate an expression with a proposition. Define $P$. –  anon Nov 10 '11 at 4:17
do you mean something along the lines of $P(k)=P(2k,k)=\frac{2k!}{(2k-k)!}$? –  Nic Young Nov 10 '11 at 4:32
Either that or as a proposition; in either case you'll have to adapt the question accordingly, because you've used it both as a proposition and as a number in the question. Also your use of parentheses is rather haphazard; there seem to be quite a number of them missing. –  joriki Nov 10 '11 at 4:42

The following is an induction argument, but the way it is written out, it doesn't look like it. We are looking at $$\frac{(1)(2)(3)(4)\cdots(2n)}{n!}$$ Separate out the odd terms on top. We get $$\frac{[(1)(3)(5)\cdots(2n-1)][(2)(4)(6)\cdots (2n)]}{n!}.$$
But $(2)(4)(6)\cdots(2n)=2^n n!$. So our quotient is $$2^n(1)(3)(5)\cdots(2n-1).$$ We conclude that $2^n$ divides our original expression. Not only that, it is the highest power of $2$ that does.

The idea can be turned into a textbook style induction. We prove that the highest power of $2$ that divides $P(2n,n)$ is $2^n$. The result is clearly true at $n=1$. Suppose it is true at $n=k$. We show that it is true at $n=k+1$. Note that $$P(2k,k)=(2k)(2k-1)\cdots (k+2)(k+1),$$ and $$P(2k+2,k+1)=(2k+2)(2k+1)(2k)\cdots (k+2).$$ Divide, noting that most of the terms cancel. We get $$\frac{P(2k+2, k+1)}{P(2k,k)}=\frac{(2k+2)(2k+1)}{k+1}=2(2k+1),$$ and therefore $$P(2k+2,k+1)=2(2k+1)P(2k,k).$$ Thus if $2^k$ is the highest power of $2$ that divides $P(2k,k)$, then $2^{k+1}$ is the highest power of $2$ that divides $P(2k+2,k+1)$.

Comment: Induction is exceedingly common, and usually not noticed. Roughly speaking, when we manipulate an expression that involves $\dots$, there is induction going on,

-
$P(2k,k)=2^k(2k-1)!!$ where $(2k-1)!!$ is the double factorial, which is odd. –  robjohn Nov 10 '11 at 11:45

I assume the problem is to show that $2^k|P(2k,k)$ for all $k\in\mathbb{Z}$, where $P(a,b)=a!/(a-b)!$, using induction. There are two major issues with what you've written: first, you refer to $P$ as if it were a proposition or hypothesis, when in reality it is an expression. Now $P =\mathrm{blah}$ is a statement, and that is the form of the theorem and the hypothesis. Second, when putting $n+1$ into the expression you made an error: you only replaced one of the $n$'s in $P(2n,n)$, when you need to replace all copies.

The correct argument might begin like:

Induction Hypothesis: $2^n|P(2n,n)$ for the particular number $n$.

Induction Step: Observe

$$P(2(n+1),(n+1))=\frac{(2n+2)!}{(n+1)!}.$$

Recall that $P(2n,n)=(2n)!/n!$; show that the above is $2$ times a multiple of $P(2n,n)$, hence $2^{n+1}$ divides the new expression $P(2(n+1),(n+1))$. Can you do this and fill in the rest?

-
Yes absolutely... They key was I looked over that the equation is $P(2(n+1),(n+1))$ not $P(2(n+1),n)$. Thank you so much for catching my oversight. –  Nic Young Nov 10 '11 at 6:26