From time to time, I may post my experience in solving a specific problem including some wrong twists and turns I’ve taken, as well as the motivation for some rather cryptic constructions. Warning : since this post documents my thought process, it’s going to be extremely, perhaps even unnecessarily, verbose. Feedback will be appreciated, e.g. is this format too chatty and long-winded? Too many detours? Or…?

Today’s problem is Question A6 of Putnam 99.

The sequence a_n for n ≥ 1 is defined as follows: a₁ = 1, a₂ = 2, a₃ = 24 and for n ≥ 4, we have:

Prove that n divides a_n for any n ≥ 1.

Ready? Here goes.

The recurrence itself looks rather daunting. Now, let’s recall what kind of tools we have for solving recurrence relations: pretty much the most useful tool is that of solving linear recurrence relations. E.g. the Fibonacci sequence defined by and for n ≥ 1 has a closed form (known as Binet’s formula). Although I’ve not described in class how one can derive the closed form, it is a useful thing to keep in mind if you don’t know about it yet. There’s also the technique of power series, which deserves an entire lecture devoted to it, and from which one can derive some pretty cool sequences like the Catalan numbers.

But I’m digressing…

In any case, the above recurrence is clearly non-linear. And the irritating thing is that during competitions, one can’t use calculators and though it’s possible to get a₄ = 1344 by a bit of paperwork, getting the next term seems out of the question. In short, we can’t get enough terms to spot a pattern (within a competition anyway).

So the next thing we attempt to do can be quite a useful trick.

Attempt to Approximate the Size of a_n

Fine, if we can’t solve it yet, see if we can’t get a handle on how fast the sequence increases. From the first 4 terms, it seems clear the rate of increase is huge. Our next observation is that: the recurrence relation for a_n is a degree-3 relation divided by a degree-2 one, i.e. it is …. almost linear??

So let’s try our usual trick for linear recurrence relations and plug in for some fixed constant α. Let’s say this is a good approximation for , then plugging in gives…

Whoa, the next term is negative? A little unbelievable from what we could observe. This just means that our sequence is not increasing fast enough, i.e. our approximate is too low.

Ok, so let’s take instead, dropping the constant since it’s clearly useless from our prior experience. This gives:

No good! Eventually the terms will still become negative so our approximation still isn’t increasing fast enough. In fact, if you try for a fixed k, the recurrence eventually goes negative – but as k increases, that cross-over point becomes further and further away.

Ok, so maybe ? We can’t handle that since is a disaster to manipulate.

Perhaps we can write and rewrite the recurrence relation in terms of b_n‘s. We get (omitting the pesky details):

This, by the way, can be a good trick : scaling down a term and writing the recurrence relation via another variable which is increasing at a more manageable rate.

In this case, this doesn’t help; we get a relation which is worse, and in fact, one can even argue that the two relations are “asymptotically identical” since as n becomes large, we can ignore (n-1)/n and (n-2)/n.

Ok, now what about the ratio between two successive terms : ? Upon writing this, we get our first breakthrough:

i.e. , starting with b₂ = 2, b₃ = 12. A linear recurrence relation!! Let’s shift the indices so that b₀ = 2, b₁ = 12, thus giving us

Shifting back the indices gives us for n ≥ 2. The problem isn’t quite solved yet since we have yet to show n divides a_n, but it looks pretty close. To patch up the gaps:

• if n=p is an odd prime, then by Fermat’s little theorem and so is a multiple of n;
• if n is divisible by p^r where p is an odd prime, then is a multiple of p for k=1,2,…,r and r(p-1) clearly does not exceed n-1;
• if n is divisible by 2^r then there’re far more than sufficient powers of 2 to go around.

Note: this article does not constitute a rigourous solution to the problem. The reader is advised to  write up the proof properly.  ◊