25th Putnam 1964

Problem A4

The sequence of integers un is bounded and satisfies un = (un-1 + un-2 + un-3un-4)/(un-1un-2 + un-3 + un-4). Show that it is periodic for sufficiently large n.



This is almost trivial. The un are bounded and integral, so there are only finitely many possible values. Hence there are only finitely many possible values for the 4-tuples (un-1, un-2, un-3, un-4). So we must eventually get a repeat. Suppose the t-tuples are the same for n = N and n = N+M. Then the recurrence relation implies that they must also be the same for n = N+1 and n = N+M+1, and for n = N+2 and N+M+2 and so on. In other words the sequence is periodic (with period M) from this point onwards.



25th Putnam 1964

© John Scholes
25 Jan 2002