# 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 .