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

Question

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!

Answer 1

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

Answer 2

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."

Answer 3

$(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 :)

Answer 4

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*}$$

Answer 5

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)!$