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.
 A: 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?
A: 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,
