On the 3rd step, I plug in (n+1) and get
(2n+1)!/(n+1)!(n+2)!
Then I transform it to
(2n+1)2n!/n!(n+1)!(n+1)(n+2)
And since I assume that (2n)!/n!(n+1)! is a natural number I make it =k, then I got
k* (2n+1)/(n+1)(n+2)
If I could prove that (2n+1)/(n+1)(n+2) is also a natural number I would be done, but I can't do anything with (2n+1)/(n+1)(n+2).
Can't, since if you plug in 1 in the first step you get 1/2 and that's not a natural number. Anyway, I realized I made a computing mistake, it should be (2n+2)!, not (2n+1)!. Then I get (2n+1)(2n+2)/(n+1)(n+2), then I can cancel out (n+1) and then I get 2*(2n+1)/(n+2). But I still can't do anything with that, tried induction as well.
I also just read that these numbers are also known as the Catalan numbers, if it helps anyone. I couldn't find any proofs on the internet.