You're nearly there - in fact, you've pretty much proved it!

You just need to use an alternative kind of induction, calledcourse of valuesinduction. 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 truefor 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.

QED!