Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.
• Meta

Function After Function. Topic: Algebra/Calculus. Level: AIME. November 20th, 2006

Problem: (1985 Putnam – B2) Define polynomials for by , for , and

for . Find, with proof, the explicit factorization of into powers of distinct primes.

Solution: As usual, we try a few small cases and look for an induction (this is important to get in the habit of, especially when an arbitrary large number is given, i.e. ). First, convert the derivative into an integral; we implicitly use the initial conditions without actually citing them in the integration. So we find that

.

By this point, you hope you have figured the pattern out because the next calculations get pretty nasty and we don’t want to go there. So we conjecture, naturally, that for all . We can show this by induction, with the base cases given above.

.

So… how do we integrate this. In fact, a common strategy can be applied here: whenever some function of is taken to a power, try substituting that function of out. Here, we use so . The new integral becomes

.

Factoring and substituting back, we get

,

completing the induction. Hence

,

which is, incidentally, the prime factorization. QED.

——————–

Comment: A really cool problem involving function recursion and a nice induction. Remember that whenever you see a recursion induction is the way to go!

——————–

Practice Problem: Solve the equation knowing that one of the solutions is real.