Use mathematical induction to prove that $ \frac{(2n)!}{(2^n)} $ is a natural number for all n $\ge $ 0.

Question

$ \frac{(2n)!}{(2^n)} $ is a natural number for all n $ \ge $ 0.

Base case: n = 1

$ \frac{(2(1))!}{(2^{1})} $ = $ \frac{2*1}{2} $ = 1

My understanding is that there could be a way to figure out the induction step by proving that $ 2^n $ divides (2n)! for all n $ \ge $ 0. However, I was also looking at how for some number k, where n + 1 = k + 1, then

$ \frac{(2(k+1))!}{(2^{k+1})} $ = $ \frac{(2k+2))!}{(2^{k+1})} $.

I just don't know if I should take this approach or choose to do something with mod. Any thoughts or help? Thank you.

Answer 1

Let it be true for $n=k$, so let $a_k=\frac{(2k)!}{2^{k}}$. Let $n=k+1$: $a_{k+1}=\frac{(2(k+1))!}{2^{k+1}}=\frac{(2k)!}{2^{k}}\cdot\frac{(2k+1)(2k+2)}{2}=a_k(2k+1)(k+1)$. If $a_k$ is an integer then $a_{k+1}$ is one too.

Answer 2

So you did it right for the base step. Now let's assume that it is true for n=k. That is, $$\frac{(2k)!}{2^{k}}$$ Now we need to show that assumption is also true for $n=k+1$. That is, we need to show that $$A=\frac{(2(k+1)!}{2^{k+1}}\in \mathbb{N}.$$ But $A$ is the same as $$\frac{((2k)!)(2k+1)(2k+2)}{2^k2}.$$ By the assumption we made, $\frac{(2k)!}{2^{k}} \in \mathbb{N}$. The rest part of $A$, which is $$\frac{(2k+1)(2k+2)}{2}$$ is also belongs to a set of natural numbers, since two numbers in the numerator are consecutive ones, and one of them has to be divisible by 2. Here we finish=)

Answer 3

The trick to induction is to somehow express the $k+1$ value in terms of the $k$ value and see what happens when we apply the proposition to the $k$ case.

So we want $\frac{(2(k+1))!}{2^{k+1}} = \frac{(2k + 2)!}{2^{k+1}} = something-to-do-with(\frac{(2k)!}{2^k})$.

Factoring out $\frac{(2k)!}{2^k}$ it's easy to see:

$\frac{(2(k+1))!}{2^{k+1}} = \frac{(2k + 2)!}{2^{k+1}} =\frac{(2k)!}{2^k}*\frac{(2k + 1)(2k+2)}{2} = \frac{(2k)!}{2^k}*(2k+1)(k+1)$.

So now.... we see where the chips fall when we apply the proposition for $k$.

$\frac{(2k)!}{2^k} = N \in \mathbb N$

So $\frac{(2(k+1))!}{2^{k+1}} = \frac{(2k)!}{2^k}*(2k+1)(k+1) = N(2k+1)(k+1) \in \mathbb N$.