Prove by induction that $ 2^{n+2}|(2n+3)! $ is true for all positive integers n

Question

I am trying to prove that

$$ 2^{n+2}|(2n+3)! $$

Is true for all all positive integers $ n $.

I started proving it by induction and shown that the base case $ n = 1$ is true. Then I proceeded to $k$: $$ 2^{k+2}|(2k+3)! \implies (2k+3)! = m2^{k+2} \implies 2^{k+2} = \frac{(2k+3)!}m$$, for some integer $m$.

Now the inductive step: $2^{k+1+2} = 2^{k+2}2 = \frac{(2k+5)!}m$ for some integer $m$.

I got stuck on this step. How would I continue to solve this?

Answer 1

You're confusing the division operation $\div$ with the divisibility relation $|$.

$$ 2^{k+2}|(2k+3)! \implies (2k+3)! = m2^{k+2} $$

This is true, except you forgot to quantify $m$. It's better to say that $2^{k+1} \mathrel| (2k+3)!$ implies there exists $m$ such that $(2k+3)! = m2^{k+2}

$$ (2k+3)! = m2^{k+2} \implies 2^{k+2} = (2k+3)!|m$$

No. I think you mean $\frac{(2k+3)!}{m}$ on the right-hand side of the second equation above. But I'm not sure that helps anyway.

You want to show that $(2(k+1)+3)! = (2k+5)!$ is a multiple of $2^{(k+1)+2} = 2^{k+3}$. That is, you want to show that $(2k+5)! = n2^{k+3}$ for some integer $n$.

Observe that $$ (2k+5)! = (2k+5)(2k+4)(2k+3)! = (2k+5)(2k+4)2^{k+2}m $$ and you want to show the right-hand side is a multiple of $2^{k+3}$. Can you do that?

Answer 2

Given $2^{k+2}|(2k+3)!$ you have $2^{k+1+2}=2\cdot 2^{k+2}$ divides $(2(k+1)+3)!=(2k+3)!(2k+4)(2k+5)$ because $2k+4$ is even and contributes at least one more factor $2$.

Answer 3

The assumption for $k$ is: $$2^{k+2}|(2k+3)!\text.$$ The inductive step is to prove, from that assumption, that: $$2^{k+3}|(2k+5)!\\ \iff (2k+5)!=2^{k+3}m\\ \iff (2k+5)(2k+4)(2k+3)!=2\times2^{k+2}m$$ for some integer $m$.

Let $(2k+3)!=m_12^{k+2}$. From the assumption, $m_1$ is an integer. So, the inductive step becomes $$(2k+5)(2k+4)m_1=2m\\ \iff\frac{(2k+5)(2k+4)m_1}2=m\\ \iff(2k+5)(k+2)m_1=m\text.$$ Consider that the left-hand side is an integer. Q.E.D.

Answer 4

Without induction, the $\,n+1\,$ numbers $\,2, 4, 6, \ldots, 2n+2\,$ are all even, and are all factors of $\,(2n+3)!\,$, so $\,2^{n+1} \mid (2n+3)!\,$. Also $\,2n+3 \ge 5\,$ so $\,4\,$ is always among the factors of the factorial, which gives an additional factor of $\,2\,$, so in the end $\,2 \cdot 2^{n+1} = 2^{n+2} \mid (2n+3)!\,$.