Thoughts on a Problem

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 an for n ≥ 1 is defined as follows: a1 = 1, a2 = 2, a3 = 24 and for n ≥ 4, we have:

a_n = \frac {6 a_{n-1}^2 a_{n-3} - 8 a_{n-1} a_{n-2}^2} {a_{n-2} a_{n-3}}.

Prove that n divides an 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 F_0 = 0, F_1 = 1 and F_{n+1} = F_n + F_{n-1} 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 a4 = 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 an

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 an 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 a_n \sim c\cdot \alpha^n for some fixed constant α. Let’s say this is a good approximation for a_{n-3}, a_{n-2}, a_{n-1}, then plugging in gives…

a_n \sim c \left[ \frac {6\alpha^{3n-5} - 8\alpha^{3n-5}} {\alpha^{2n-5}} \right] = -2c \alpha^n.

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 a_n \sim n! instead, dropping the constant since it’s clearly useless from our prior experience. This gives:

a_n \sim \frac{6(n-1)!^2 (n-3)! - 8(n-1)!(n-2)!^2} {(n-2)! (n-3)!} = 6(n-1)! (n-1) - 8(n-1)! (n-3) = (n-1)! (-2n+18)

No good! Eventually the terms will still become negative so our approximation still isn’t increasing fast enough. In fact, if you try a_n \sim (kn)! 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 (n^2)!? We can’t handle that since (n^2)! / (n-1)^2! is a disaster to manipulate.

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

b_n = \frac { 6 \left( \frac{n-1}n\right) b_{n-1}^2 b_{n-3} - 8 \left( \frac{n-2}n \right) b_{n-1} b_{n-2}^2} {b_{n-2} b_{n-3}}.

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 : b_n = a_n / a_{n-1}? Upon writing this, we get our first breakthrough:

b_n = \frac {a_n} {a_{n-1}} = \frac {6 a_{n-1} a_{n-3} - 8 a_{n-2}^2}{a_{n-2} a_{n-3}} = 6 \frac {a_{n-1}} {a_{n-2}} - 8 \frac {a_{n-2}} {a_{n-3}}

i.e. b_n = 6 b_{n-1} - 8 b_{n-2}, starting with b2 = 2, b3 = 12. A linear recurrence relation!! Let’s shift the indices so that b0 = 2, b1 = 12, thus giving us

b_n = 4\cdot 4^n - 2\cdot 2^n = 4^{n+1} - 2^{n+1}.

Shifting back the indices gives us a_n = \prod_{i=2}^n (4^{n-1} - 2^{n-1}) for n ≥ 2. The problem isn’t quite solved yet since we have yet to show n divides an, but it looks pretty close. To patch up the gaps:

  • if n=p is an odd prime, then by Fermat’s little theorem 4^{n-1} \equiv 1 \pmod n and 2^{n-1} \equiv 1 \pmod n so 4^{n-1} - 2^{n-1} is a multiple of n;
  • if n is divisible by pr where p is an odd prime, then 4^{k(p-1)} - 2^{k(p-1)} 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 2r 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.  ◊

This entry was posted in Thought and tagged , , , . Bookmark the permalink.

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