Put , and
Then and so the base case holds.
Now suppose for some , then:
The first of the terms is divisible by by assumption, and as a odd power of two is congurent to modulo and its square is congruent to modulo the second factor is divisible by and so we have is divisible by .
Which allows us to conclude by mathematical induction that is divisible by for any