Even Pascals
Let , where k is an integer. Prove that for any positive integer n the number
is divisible by .
- 14 August, 2012 -
- Article, Math Problems -
- Tags : algebra, analysis, number theory, titu
- 0 Comments
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 .