## Monday, November 20, 2006

### 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.