On 2012 Putnam Problem A3

This post continues my effort to write detailed solutions to the problems on this year’s Putnam exam (previous solutions are here and here). More than the actual solutions, I hope that students will find my commentary valuable. When writing these, I try to emphasize the thought processes and the strategies that were used to solve the problem, so that a reader might feel empowered to solve similar problems. I feel like some of the solutions in the MAA’s Putnam Directory are too slick and might reinforce a student’s feeling that they never would have come up with a solution on their own. These solutions attempt to counter that feeling.

Anyway, here is problem A3: Let $f: [-1,1] \to \mathbb{R}$ be a continuous function such that

$f(x) = \frac{2-x^2}{2} f \left(\frac{x^2}{2-x^2}\right)$ for every $x$ in $[-1,1]$ ,
$f(0) = 1$ , and
$\lim_{x \to 1^-} \left( \frac{f(x)}{\sqrt{1-x}} \right)$ exists and is finite.

Prove that $f$ is unique, and find a closed-form description of $f(x)$ .

Spoiler alert: the solution is below Nyan Cat.

Initial remarks

Something that makes this problem different from most Putnam problems is that it has two completely separable parts. One part is to prove that $f$ is unique, and the other is to find a closed-form description of $f(x)$ . It’s quite possible that each part is worth 5 points, which means that you could have earned substantial partial credit for doing only one part of the problem.

Solution, Part 1

I’ll start with what I think is the easier part of the problem — the closed-form description. But before I get into the solution, perhaps I should elaborate on what “closed-form” actually means. It’s just a fancy way of saying that they want an explicit formula for $f(x)$ . “Closed-form” excludes the possibility of implicit descriptions (such as the three conditions in the problem) or infinite descriptions (involving power series or limits).

The great thing about this part of the problem is that it doesn’t matter at all how you come up with the formula for $f(x)$ . It’s good enough to say “I guessed it”, as long as you check that your guess satisfies the three conditions. And, although I don’t think random guessing is a good idea, I really do think that educated guessing is the best way to arrive at the answer. Let me describe how I came up with it.

From the three conditions, you can see that $f$ satisfies the following properties:

From condition 1, you can see that $f$ is an even function, since the right side of the equation only depends on $x^2$ .
From condition 3, you can see that $f(1) = 0$ , and in fact, you can go farther and say that $f(x)$ goes to zero in a similar manner to how $\sqrt{1-x}$ goes to zero (in particular, it will have a vertical tangent line).

Also, even though it’s not a consequence of the conditions, it’s reasonable to guess that the formula for $f(x)$ isn’t well-defined outside the interval $[-1,1]$ (which would typically happen because of a square root).

Finally, I’d say it’s reasonable to guess that $f(x)$ is a familiar function. My reason for saying this isn’t really mathematical, but rather psychological. The people who write the Putnam want the problems to be interesting. If the statement of the problem looks ugly (like this one does), then you should expect the answer to be “nice”.

Putting all these ideas together, there’s only one reasonable guess I can come up with: $f(x) = \sqrt{1-x^2}$ . It’s an even function, $f(0) = 1$ , it goes to zero with a vertical tangent as $x \to 1$ , and it’s a nice, familiar function (its graph is the top half of the unit circle).

So, like I said, it’s good enough to say “the answer is $f(x) = \sqrt{1-x^2}$ ,” as long as you check that it satisfies the conditions. Condition 2 is obvious. For condition 3, observe that

$\frac{f(x)}{\sqrt{1-x}} = \sqrt{1+x}$ ,

which does have a finite limit as $x \to 1^-$ . And condition 1 is a longish but straightforward computation:

$\frac{2-x^2}{2} f\left( \frac{x^2}{2-x^2} \right) = \frac{2-x^2}{2} \sqrt{1 - \frac{x^4}{4 -4x^2 + x^4}} = \frac{2-x^2}{2} \sqrt{\frac{4-4x^2}{(2-x^2)^2}} = \sqrt{1-x^2}.$

And that’s enough to show that $f(x) = \sqrt{1-x^2}$ is the answer.

Solution, Part 2

As a general rule in mathematics, the way to prove something is unique is to start by assuming that there are two of them, and then prove that those things are equal. So, in this case, you can assume there are two functions, $f$ and $g$ , that satisfy the conditions. And, to prove $f = g$ , it’s often more convenient to prove $f - g = 0$ .

So, let $h = f - g$ . If $f$ and $g$ satisfy the three conditions, then $h$ will also satisfy conditions 1 and 3. However, instead of condition 2, we have $h(0) = 0$ . Our goal will be to prove that $h(x) = 0$ for all $x$ in $[-1,1]$ .

Let $a$ be an arbitrary number in $[0,1]$ . (Since $h$ is even, we can disregard negative values in the domain.) We want to prove that $h(a) = 0$ .

Condition 1 tells us that

$h(a) = \frac{2-a^2}{2} h \left( \frac{a^2}{2-a^2} \right).$

Since $a$ is between 0 and 1, we can see that $\frac{2-a^2}{2}$ is between 1/2 and 1, meaning that $h(a)$ is the same sign as, but with absolute value less than or equal to, $h \left( \frac{a^2}{2-a^2} \right)$ . This step can be repeated indefinitely. To simplify notation, we can recursively define a sequence

$a_0 = a,$

$a_{n+1} = \frac{a_n^2}{2-a_n^2}.$

By repeating the above step, we get $|h(a)| = |h(a_0)| \leq |h(a_1)| \leq |h(a_2)| \leq \dots$ . But we can show that the sequence $\{a_n\}$ converges to 0 (except for when $a = 1$ ); the proof of this convergence is in the “appendix” below. Since $h$ is continuous, $\{h(a_n)\}$ converges to $h(0) = 0$ , so the above sequence of inequalities implies that $h(a) = 0$ , as desired.

As a minor technical note, we excluded $a=1$ from the above argument, but $h(1)$ must be 0 because of continuity (you can also deduce it from condition 1 or condition 3).

QED

Appendix

I wanted to separate the proof of convergence of the above-defined sequence $\{a_n\}$ , since the technique is an important one to have in your “toolbox”. There actually are two steps to it. First, prove that it converges. Second, prove that the limit is zero.

To prove it converges, you can employ a useful theorem: Any bounded, monotonic sequence converges. Here, “bounded” means that all the terms of the sequence are between two fixed numbers A and B. And “monotonic” means that the terms in the sequence only move in one direction, either increasing or decreasing. In this case, all the terms of the sequence are between 0 and 1 (you can easily prove this by induction), and it is monotonically decreasing. To see this, we can compare

$a_n$ versus $a_{n+1} = \frac{a_n^2}{2-a_n^2}$ .

If $a_n = 0$ , then both sides are equal. Otherwise, $a_n > 0$ , and it’s okay to divide both columns by $a_n$ to get

$1$ versus $\frac{a_n}{2-a_n^2}$ .

The right side is always smaller when $a_n < 1$ , and that proves the sequence is monotonically decreasing.

To prove the limit is 0, you use the fact that the limit $L$ will satisfy the equation in the recurrence

$L = \frac{L^2}{2-L^2}$ .

(This is a really useful trick for finding limits.) This equation is cubic, with solutions 0, 1, and -2, so the limit must be one of these solutions. But, since we know all the terms are between 0 and 1, and they are decreasing, the limit has to be 0.

QED

Closing remarks

If you read the solution carefully, you’ll notice that condition 3 wasn’t actually necessary to prove uniqueness. This actually bothered me for a while and made me think I was missing something. Usually you wouldn’t expect Putnam problems to include unnecessary assumptions like this. And, actually, I’m still a little bit perplexed by it. The only thing I can think of is that it’s there to provide an extra clue toward finding the formula for $f(x)$ .

supermathematics

SPACE ODDITY