Proving that a fraction is a natural number for all $n\in N$

Question

I am to prove by induction that $$\frac{(2n)!}{n!(n+1)!}$$ is a natural number for all $n\in N$. Checking the base case, assuming that the fraction indeed is a natural number I thought that I could show that the fraction is a natural number for $n+1$ by showing that it is a nonnegative (or positive, if you define naturals without $0$) integer. It is trivial to see that the fraction is never negative, but the part that is bugging me is showing that it is a whole number. Starting for $n+1$ $$\frac{(2n+2)!}{(n+1)!(n+2)!}=\frac{(2n+2)(2n+1)(2n)!}{(n+1)n!(n+2)(n+1)!}=\frac{(2n+2)(2n+1)}{(n+1)(n+2)}\cdot\frac{(2n)!}{n!(n+1)!}$$ Here I use the IH, and I conclude that the first fraction must be whole for the whole product to be whole, since we have a form of $x=ky$ where $y\in N$ and we want $x\in N$ therefore $k\in N$ as well. So i continue to prove that $k$ is whole number and I reduce that to showing that $$\frac{2n+1}{n+2}\in N$$ however this isn't whole? Where is my mistake? How do I continue?

Answer 1

Let's try with an example. Take $n=5$. Then $$\frac {10!}{5!6!}=42$$ and $$\frac {12!}{6!7!}=132$$

The quotient $132/42$ is not an integer, so you can not prove the statement this way, because the final step is false.

If you still want (or have) to use induction, you should try to change the strategy. (I'm thinking on it...)

Answer 2

There's no reason it should be an integer. Just because $a=bc$, and $a$ and $c$ are integers, doesn't mean that $b$ needs to be an integer. In fact, take a simple example; put $n=7$, then $$\frac{(14)!}{7!8!} = 429$$ but $$\frac{(2\cdot7 + 2)(2\cdot7 + 1)}{(7+1)(7+2)}=\frac{15\cdot16}{8\cdot 9}=\frac{240}{72}=\frac{10}{3}\notin \mathbb N$$