The base case is true by assumption, now assume that for some we have is an integer for all .

Now consider:

if you examine the expansion you will find that pairs of terms can be grouped together to give integers by the induction hypothesis (with possibly an unpaired middle term which will be an integer on its own) except for the first and last terms which together are:

Hence as is an integer as are all the other terms by the induction hypothesis so is [tex]u_{k+1}[/tex] and so the proof follows by strong induction.

CB