You're nearly there - in fact, you've pretty much proved it!
You just need to use an alternative kind of induction, called course of values induction. It works along these lines:
This assumes more, but it's a perfectly valid way to do induction.
- Say is the statement you need to prove for all n.
- Base case: Show .
- Induction step: Assume is true for ALL ; then show .
In your case:
The base case has been given already.
For the inductive step, you rightly considered the expression
You know the LHS is an integer, and by course of values induction, is an integer.
(We can assume , as well as !)
Hence, is an integer, as on the RHS, integer + integer = integer.