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.

  • $\begingroup$ @AdamHughes they are asking for $$ \nu_2 ((2n)!) - \nu_2 (n!) $$ which follows from Legendre's rule en.wikipedia.org/wiki/Legendre's_formula $\endgroup$ – Will Jagy Feb 22 '17 at 2:42
  • $\begingroup$ @WillJagy ah, OK, I can see it now. Thanks for that! $\endgroup$ – Adam Hughes Feb 22 '17 at 2:45
  • 1
    $\begingroup$ @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. $\endgroup$ – Will Jagy Feb 22 '17 at 2:48
  • 1
    $\begingroup$ @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. :) $\endgroup$ – Adam Hughes Feb 22 '17 at 2:59
  • 1
    $\begingroup$ @AdamHughes found my early version math.stackexchange.com/questions/141196/… $\endgroup$ – 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.

  • $\begingroup$ 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$ $\endgroup$ – Will Jagy Feb 22 '17 at 2:52
  • $\begingroup$ @WillJagy Thanks. I don't tend to think of Legendre's formula as an inductive statement...interesting! $\endgroup$ – lulu Feb 22 '17 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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