Let , where k is an integer. Prove that for any positive integer n the number
is divisible by .
1. Find a closed form expression of
We start with the construction of .
Since the first term of our series is a one, and the terms alternate in sign on odd powers, we should only consider polynomials
Okay, but we still can’t completely remove the odd terms from the combinations. However, we see that if we were to add in another polynomial of the same degree, we can match up the terms so that the coefficients on the odd are canceled. That is, we find the pair such that
In order to get , we need to set
From this, we get the closed form expression of .
2. Find a recurrence relation for
This may seem counter-intuitive, but the problem looks like one that can be solved via induction on , which is much easier to do on a linear recurrence.
Recall from earlier and differential equation that is of the form of a linear recurrence with characteristic polynomial whose roots are . Let’s construct this polynomial in order to find the recurrence.
Recall that the characteristic polynomial of is , therefore, is the characteristic polynomial associated with
3. Show that
As brought up previously, we will prove this by induction on . Let , we will show that
This concludes our proof that .