How to prove by Principle of Induction?

Question

Prove by principle of induction that $$\frac{(2n)!}{2^n n!}$$ is odd for all $n\in\mathbb{N}$.

Answer 1

Hint:

If $f(m)=\dfrac{(2m)!}{2^m\cdot m!}$

$$\dfrac{f(n+1)}{f(n)}=\cdots=2n+1$$ which is odd

$f(1)=?$

Answer 2

First show $f(1)$ is odd. This equals $\frac{2!}{2^1 1!} = \frac{2}{2}=1$, so that checks out.

Now suppose that for some $n$, $f(n)$ is odd. We need to show that $f(n+1)$ is odd.

By definition: $f(n+1) = \frac{2(n+1)!}{2^{n+1} (n+1)!}$. You should know that $2^{n+1}=2 \cdot 2^n$ and $(n+1)! =(n+1)n! $ and $(2n+2)! = (2n+2)(2n+1)(2n)! = 2(n+1)(2n+1)(2n)!$.

So $$f(n+1) = \frac{2(n+1)(2n+1)(2n)!}{(2^n n!)2(n+1)} = (2n+1)f(n)$$

as all other terms cancel. Then $f(n+1)$ is odd as the product of two odd integers $2n+1$ and $f(n)$.

This completes the induction step and hence the proof.