EDIT: So I started the blogging marathon, “One a day”, in the original post a bit too soon. I’ll keep you posted on when it will actually begin. I am currently in China doing a lot of nice work on the wave equation, can’t wait to tell you all about it!
Today we will look at a Putnam Problem, here is the question, (screenshot from the problem sheet that can be found here).
Now first looking at this problem you probably think induction is a good place to start. It isn’t. The reason that it is really hard to begin with induction is dividing polynomials by other polynomials is hard – let alone ensuring that the resulting quotient has integer coefficients and no remainder terms. So, let’s make life easier and re-write the recurrence relation so that it has no division in there (a good first step for solving problems!). So we note that the recurrence relation can be re-arranged to
Now, you can try and pull induction on 1, I encourage you to. That way you will find that it just reverts back to dealing with a quotient and the simplification step we just did get’s undone. So what to do next?
Well, a good next step is to put all our terms on one side.
Now from this step, it requires a lot of thinking; or rather one little observation. It is remarkable that no matter what you pick, the left hand side of 2 is identically zero. These are all different polynomials, but combining them as in 2 yields . In particular, if we chose instead of , the recurrence relation is now
and after collecting terms we get
Now 5 is telling us that both sides of the equation must equal a constant if this is to be true for all values of , after all they are not the same polynomials. So you can now go ahead and substitute in to find what this constant has to be. However, if you go ahead and do it, you’ll hit a dead end, but I encourage you to go down this path to see exactly what the dead end. There is one more thing to do with 5 before we find what the constant is, and that is divide by the factors, (once you see the dead end I talked about, you’ll understand why it is necessary to divide). So dividing through by the factors, which are non-zero polynomials,
Now substituting in and we can see that the constant factor is
And so now we get a new recurrence relation for our polynomial
which can be arranged to give
which is clearly a polynomial with integer co-efficients. Hopefully I’ve shown you the problem solving process involved in attacking a question like this. The biggest piece of advice you can take from this problem is at first try something, and if it doesn’t work, analyse why and see if you can avoid it or change your game plan to fix it!