# How can I prove that $2^{n+2}\mid(2n+3)!$?

I'm not sure where to proceed or how to go about proving this assertion holds for all natural numbers n: $$2^{n+2} \mid(2n + 3)!$$

The base case is $n=1$, where $2^{1+2}\mid(2\cdot 1+3)!$ which simplifies to $8 \mid 120$, and 8 does indeed divide 120.

Again, we shall assume the statement is true for $n = k$. $$2^{k+2}\mid(2k+3)!$$ Then we shall prove that the statement must be true for n = k + 1: $$2^{k+3}\mid (2(k+1)+3)!=(2k+5)!$$
Sorry for the poor formatting, this is the first time I've posted here. I'm not sure if I've started off on the right path, or where to go next. Any suggestions would be lovely!

There are $n+1$ even numbers in $1,\cdots,2n+3$ and one of them is $4$ (given $n\ge1$).

• So because the divisor has 2 to the power of whatever, it will always divide whatever the quotient is due to it having a 4 in the factorial? Is this the correct way to interpret your response? – knames Jul 3 '14 at 0:09
• @knames You use the phrases "the divisor" and "whatever" and "it" and "the quotient" but I don't know what you're referring to with these phrases. Please be clear and specific. – blue Jul 3 '14 at 0:10
• the divisor being 2^(n+2) and the quotient being (2n+3)!. The left part before | will always divide the right part after | because the right part has a 4 in the factorial? – knames Jul 3 '14 at 0:12
• @knames The word "quotient" refers to what you get after you've divided, it doesn't refer to the thing you're dividing. Just because something is divisible by $4$ does not mean it is divisible by $2^{n+2}$; that's where the total of $n+1$ even numbers comes in. Try thinking some more about my hint. – blue Jul 3 '14 at 0:14
• This is as explicit as I can make it: $$(2n+3)!=1\cdot2\cdot3\cdots(2n+3)=(\underbrace{2\cdot\color{Red}4\cdots2n+2}_{n+1~\rm numbers})(1\cdot3\cdots2n+3)$$ $$=2^{n+1}(1\cdot\color{Red}2\cdot3\cdots n+1)(1\cdot3\cdots 2n+3)=2^{n+2}(3\cdots n+1)(1\cdot3\cdots 2n+3).$$ Honestly, I thought my hint was pretty clear and straightforward, and this level of explication was totally unnecessary. – blue Jul 3 '14 at 0:41

$(2k+5)!=(2k+5)(2k+4)(2k+3)!=(2k+5)(2k+4)2^{k+2}\cdot c$ where the last equality is due to $2^{k+2}\mid (2k+3)!$ which you assume.

Hence, $(2k+5)!=(2k+5)(k+2)(2)(2^{k+2})$. Finish it :)

We have $(2k+5)!=(2k+3)!(2k+4)(2k+5)$. Since by the induction hypothesis, $2^{k+2}$ divides $(2k+3)!$, and since $2$ divides $2k+4$, we conclude that $2^{k+3}$ divides $(2k+5)!$.

Remark: (This refers to an earlier version of the post.) In writing up a proof, never try to travel from what you want to show to something "known."

• I'm new to number-theory, could you elaborate on what you meant by "In writing up a proof, never try to travel from what you want to show to something "known."" – knames Jul 2 '14 at 23:56
• @knames Sometimes you start from the fact that you're trying to prove and manipulate things until you've arrived at an already established fact. This is how it goes in any kind of math, number theory or no. You might even try burning both ends of the stick and meeting somewhere in the middle. At the end, though, when you actually go to write down your proof, you need to start at something known and end up at the desired claim, in that order. – blue Jul 3 '14 at 0:00
• In high school, people pick up the very bad habit of writing down what they want to be true, and then manipulating until they get something true, like $x=x$. This is logically wrong, unless one shows that every step that got us from what we want to $x=x$ is reversible. If one showed reversibility (which one often cannot show), it would be OK. But people who go from the desired to something known often lose control over the logic of the argument, and end up writing a confused circular non-proof. I am not saying you shouldn't fool around informally with the "desired." – André Nicolas Jul 3 '14 at 0:01
• But ultimately the written up argument must go "the right way" so that its validity is clear. – André Nicolas Jul 3 '14 at 0:02
• @blue, @ André Nicolas Thank you, this makes sense to me now! – knames Jul 3 '14 at 0:03

Start with $2k+2∣(2k+3)!$. This means there exists a $b \in\mathbb{N}$ such that $(2k+3)! = b2^{k+2}$.

\begin{align*} (2k+3)! = b2^{k+2} & \Rightarrow (2k+3)!(2k+4)(2k+5) = b2^{k+2}(2k+4)(2k+5)& \\ & \Leftrightarrow (2k+5)! = b2^{k+2}2(k+2)(2k+5) \\ & \Leftrightarrow (2k+5)! = (b(k+2)(2k+5))2^{k+3} \\ & \Rightarrow 2^{k+3} | (2k+5)! \\ & \Leftrightarrow 2^{(k+1)+2} | (2(k+1)+3)! \end{align*}

• Just a quick question, what is the significance of including the last line? Why break down the exponent and everything to the right of the "|"? – knames Jul 3 '14 at 1:25
• It makes the induction pedantically clear. This expression is a straight substitution of $(k+1)$ for $k$ in the equation we're trying to prove. – NovaDenizen Jul 3 '14 at 1:42

## Theory

The number of factors of the prime number, p, that divide into n! is $\sum_{i=1}^{\infty} \left \lfloor \dfrac{n}{p^i} \right \rfloor$

As formidable as this equation may look, it's not really that bad.

First of all, once $\left \lfloor \dfrac{n}{p^i} \right \rfloor$ becomes $0$, all of the terms after that are also $0$. So it's really a finite sum.

Second, it can be shown that $$\left \lfloor \dfrac{n}{p^{i+1}} \right \rfloor = \left \lfloor \dfrac{\left \lfloor \dfrac{n}{p^i} \right \rfloor}{p} \right \rfloor$$

So, knowing the value of $\left \lfloor \dfrac{n}{p^i} \right \rfloor$ makes it easier to compute $\left \lfloor \dfrac{n}{p^{i+1}} \right \rfloor$.

## Application

We make the following computations.

• $\left \lfloor \dfrac{2n+3}{2} \right \rfloor = n+1$
• $\left \lfloor \dfrac{n+1}{2} \right \rfloor \ge 1 \quad (\forall n \ge 1)$

It follows that the highest power of 2 that divides into $(2n+3)!$ is greater than or equal to $(n+1) + 1 = n+2$. In other words, $2^{n+2} | (2n+3)!$