# Induction involving primes

Use induction to prove that for every positive integer $n$, when we factor the product $$(n+1)(n+2)...(2n-1)2n$$ into primes, there are exactly $n$ copies of the prime $2$.

I do not really understand what the question is asking.

• @AdamHughes they are asking for $$\nu_2 ((2n)!) - \nu_2 (n!)$$ which follows from Legendre's rule en.wikipedia.org/wiki/Legendre's_formula – Will Jagy Feb 22 '17 at 2:42
• @WillJagy ah, OK, I can see it now. Thanks for that! – Adam Hughes Feb 22 '17 at 2:45
• @AdamHughes, I like this question. I wrote a proof of Legendre's formula strictly using induction in an answer on this site. I seem not to have saved the link. Good exercise, though not difficult. – Will Jagy Feb 22 '17 at 2:48
• @WillJagy yeah, it's a cute exercise, I agree. I always go the counting route, but then that's my analytic background showing through, I like the idea of an inductive proof a lot now that this question notes that the approach is quite straight-forwardly viable. :) – Adam Hughes Feb 22 '17 at 2:59
• @AdamHughes found my early version math.stackexchange.com/questions/141196/… – Will Jagy Feb 22 '17 at 3:32

Let $P_n$ be your number. We want to show that $2^n\,||\,P_n$. That is, we want to show that $2^n$ divides $P_n$ but $2^{n+1}$ does not. It is easy to check that this is true if $n=1$ ($P_1=2$) or if $n=2$ (as we have $P_2=3\times 4 = 12$).
Let us assume that we have settled the point for $P_n$. Thus we can write $P_n=2^nM$ for some odd $M$. Inductively, we now want to address the issue for $P_{n+1}$.
Specifically, we want to show that $2^{n+1}\,||\,P_{n+1}$. Of course we have $$P_{n+1}=\frac {(2n+1)(2n+2)}{n+1}P_n=2(2n+1)P_n=2(2n+1)\times 2^nM=2^{n+1}(2n+1)M$$
As $(2n+1)M$ is odd, we see that we are done.
• note that Legendre's formula, for any fixed prime, can be proved by induction. en.wikipedia.org/wiki/Legendre's_formula And this problem is a consequence of Legendre's formula for prime $2$ – Will Jagy Feb 22 '17 at 2:52