I’m a dirty liar

I hate to admit it, but it’s true. Why? Because I misleadingly stated that this blog contained math and shit, but so far it’s only shit. I am truly sorry.

Starting today, however, I’m going to try and make an honest man of myself. Every day (hopefully, but not likely), I’ll try to solve at least three interesting problems, and post my solutions on here. Most of these problems will have solutions that you can just look up, so in order to make myself marginally useful, I will include not only my solutions but also how I came by these solutions. I personally find this much more informative and helpful than reading a beautiful, elegant solution which appears to be conjured out of nowhere and which I never would have known how to come by on my own. Posting will also hopefully give me a better way to keep track of my progress, and maybe motivate me to actually keep working. Anyway, we’ll start off simple. I’m going to go through these “easy problems” first.

2014-A1. Prove that every nonzero coefficient of the Taylor series of (1-x+x^2)e^x about x = 0 is a rational number whose numerator (in lowest terms) is either 1 or a prime number.

It’s going to be hard to make any progress on this without knowing the Taylor series in question, so we should get that sorted out first. I’m not sure how much rigor the Putnam requires, but regardless I’m not going to prove that the Taylor series of the product is the product of the individual Taylor series. It’s not very hard and it’s more trouble to write out than it’s worth. Anyway, we compute the product:

(1-x+x^2)e^x = (1-x+x^2)\sum_{n=0}^\infty \frac{x^n}{n!} = \sum_{n=0}^\infty \frac{x^n-x^{n+1}+x^{n+2}}{n!}

We want to simplify things a little bit, so we group like terms. The x^n term is going to involve (n-2)! so we will have to separate the constant and linear terms. We get

= 1 + \sum_{n=2}^\infty \left(\frac{1}{n!}-\frac{1}{(n-1)!}+\frac{1}{(n-2)!}\right)x^n

Putting these three fractions over a common denominator, we see that the nth coefficient is

\frac{1-2n+n^2}{n!} = \frac{(n-1)^2}{n!} = \frac{n-1}{n(n-2)!}

for n > 2. (The coefficients of the constant and linear terms both meet the conditions so we don’t need to worry about them.)

At this point, I got a little caught up. We’re trying to prove something for all positive integers, and we have a formula to work with, so my first thought was to try induction. I monkeyed around for the bit:

Induction disaster

Yikes.

Maybe someone else can drag something useful out of this, but I can’t. So I abandoned this approach and started looking for another angle.

We want our numerator to be a prime or 1, so we should try to take advantage of the fact that the factorial in the denominator should cancel most of the factors in the numerator. We’ll proceed by casework.

1. n-1 is prime. There’s nothing to cancel it in the denominator, but we’re done anyway.

2. n-1 is composite. This actually breaks down into two sub-cases:

  • If n-1=pq, where p and q are distinct integers both greater than 1, then they will both be found in the product (n-2)!, and so the numerator will be 1 when reduced to lowest terms.
  • n-1=p^2 for some prime p. This is the only case where a composite number can’t be written as above. We’re okay in this case too, though, because one of the p factors will be canceled by (n-2)! and our numerator is prime.

This concludes the proof. Not a very hard problem, but for me it was a good exercise in knowing when to give up on an approach and try something new.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s