## Saturday, September 9, 2006

Problem: (2002 Putnam - A1) Let $k$ be fixed positive integer. The $n$-th derivative of $\frac{1}{x^k-1}$ has the form $\frac{P_n(x)}{(x^k-1)^{n+1}}$, where $P_n(x)$ is a polynomial. Find $P_n(1)$.

Solution: From the looks of this (and testing it), the derivative turns out to be really nasty and no fun at all. So let's try simplifying it using the notation they give us (i.e. the $P_n(x)$ polynomials).

If the $n$-th derivative is $\frac{P_n(x)}{(x^k-1)^{n+1}}$, then the $(n+1)$-th derivative is, by the quotient rule,

$\frac{P^{\prime}_n(x)(x^k-1)^{n+1}-P_n(x)(n+1)(x^k-1)^nkx^{k-1}}{(x^k-1)^{2n+2}} = \frac{P^{\prime}_n(x)(x^k-1)-P_n(x)(n+1)kx^{k-1}}{(x^k-1)^{n+2}}$

after we cancel $(x^k-1)^n$. But this basically gives us a recursive relationship between $P_{n+1}(x)$ and $P_n(x)$...

$P_{n+1}(x) = P^{\prime}_n(x)(x^k-1)-P_n(x)(n+1)kx^{k-1}$

$P_{n+1}(1) = P_n(1)(n+1)(-k)$.

Wow. That looks good. Seems that we're almost there. Setting $P_0(1) = 1$ (no derivatives), we can easily show by induction that

$P_n(x) = (-k)^n \cdot n!$,

finishing the problem. QED.

--------------------

Comment: Looked a lot more difficult than it actually was, especially with the ugly derivatives. After we figured out that the quotient rule allowed us to derive a simple recursion, it was basically done from there. Solving for the sequence should be clear that a factorial results from the $(n+1)$ term in the recursive definition.

--------------------

Practice Problem: (2002 Putnam - B1) Shanille Oâ€™Keal shoots free throws on a basketball court. She hits the first and misses the second, and thereafter the probability that she hits the next shot is equal to the proportion of shots she has hit so far. What is the probability she hits exactly $50$ of her first $100$ shots?