Function After Function. Topic: Algebra/Calculus. Level: AIME.

Problem: (1985 Putnam - B2) Define polynomials $ f_n(x) $ for $ n \ge 0 $ by $ f_0(x) = 1 $, $ f_n(0) = 0 $ for $ n \ge 1 $, and

$ \frac{d}{dx} f_{n+1}(x) = (n+1)f_n(x+1) $

for $ n \ge 0 $. Find, with proof, the explicit factorization of $ f_{100}(1) $ 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. $ 100 $). First, convert the derivative into an integral; we implicitly use the initial conditions without actually citing them in the integration. So we find that

$ \displaystyle f_1(x) = \int f_0(x+1)dx = \int 1dx = x $

$ \displaystyle f_2(x) = 2 \int f_1(x+1)dx = 2 \int (x+1)dx = x^2+2x = x(x+2) $

$ \displaystyle f_3(x) = 3 \int f_2(x+1)dx = 3 \int (x^2+4x+3) dx = x^3+6x^2+9x = x(x+3)^2 $

$ \displaystyle f_4(x) = 4 \int f_3(x+1)dx = 4 \int (x^3+9x^2+24x+16)dx = x(x+4)^3 $.

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 $ f_n(x) = x(x+n)^{n-1} $ for all $ n \ge 1 $. We can show this by induction, with the base cases given above.

$ \displaystyle f_{n+1}(x) = (n+1) \int f_n(x+1)dx = (n+1) \int (x+1)(x+n+1)^{n-1} dx $.

So... how do we integrate this. In fact, a common strategy can be applied here: whenever some function of $ x $ is taken to a power, try substituting that function of $ x $ out. Here, we use $ u = x+n+1 $ so $ du = dx $. The new integral becomes

$ \displaystyle f_{n+1}(x) = (n+1) \int (u-n)u^{n-1}du = (n+1) \int (u^n-nu^{n-1})du = u^{n+1}-(n+1)u^n $.

Factoring and substituting back, we get

$ f_{n+1}(x) = u^n(u-n-1) = (x+n+1)^n(x+n+1-n-1) = x(x+n+1)^n $,

completing the induction. Hence

$ f_n(x) = x(x+n)^{n-1} \Rightarrow f_{100}(1) = 101^{99} $,

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 $ 2z^3-(5+6i)z^2+9iz+(1-3i) = 0 $ knowing that one of the solutions is real.