Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

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,

share|cite|improve this answer
$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


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?

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.