3. Functional equations
Of course it has to be functional equations as they beg for growth rate checking. Among those degree checking is probably the most common approach.
Example 7. Find all real polynomials $P(x)$ satisfying $(x-8)P(2x) = 8(x-1)P(x)$.
Suppose the leading term is $a_nx^n$ equating the $x^{n+1}$ term gives $2^na_n = 8a_n$ so $n = 3$, and the polynomial has to be cubic.
Simple substitution shows $P(2)=P(4)=P(8)=0$. Why do we find these roots? It starts from $P(1)$ and doubling using the formula. Since $P$ is cubic we have the general solution $P(x) = c(x-2)(x-4)(x-8)$. Note that it also includes the special solution $f=0$.
Frequency alteration usually strong hint degree chasing.
Example 8. (IMO 2004 Q2) Find all real polynomials $f$ such that $f(a-b)+f(b-c)+f(c-a) = 2f(a+b+c)$ for any reals $a,b,c$ satisfying $ab+bc+ca=0$.
By linearity it suffices to check the monomial $x^n$ only (exercise). One also shows that only even power works, with $x^2$ and $x^4$ working by substitution (and that $x^6$ doesn't for those curious). It is clear that we just need to find a bound for the degree.
It is not obvious to find examples fulfilling $ab+bc+ca=0$, but for IMO you have all the time to do that. One approach is the tuple of $(a,b,c) = t(6,3,-2)$ giving $f(3t)+f(5t)+f(8t)=2f(7t)$. Since $3^n+5^n+8^n=2\cdot 7^n$ is false when $n\geq 5$ our job is done.
One even better tuple would be $(a,b,c) = t(1-\sqrt{3}, 1, 1+\sqrt{3})$. That gives $2P(-\sqrt{3}t)+P(2\sqrt{3}t) = 2P(3t)$ and the equation $2(-\sqrt{3})^n+(2\sqrt{3})^n = 2\cdot 3^n$ which has no odd solution with LHS strictly larger than RHS when $n \geq 6$. (Solution credit to AoPS)
In all, the solution would be the family $f(x) = Ax^2+Bx^4$.
More often than not, degree chasing is hidden within the details...
Example 9. (IMO 1992 Q2) Find all real functions satisfying $f(x^2+f(y)) = y + f(x)^2$ for all real $x,y$.
Putting $x=0$ we get $f(f(y)) = y + f(0)^2$ yelling two facts: $f$ is surjective and very, very likely just linear with linear coefficient 1.
With our educated guess it takes minimal effort to conclude that $f$ is also injective and $f(0) = 0$ (which saves us the trouble), hence $f(x) = x$ is the only solution.
Let's ramp up and look at Putnam problems.
Example 10. (Putnam 2016 B5) Find all functions $f:(1,\infty)\to (1,\infty)$ with the following property: if $x,y\in (1, \infty)$ with $x^2\leq y \leq x^3$ then $f(x)^2 \leq f(y) \leq f(x)^3$.
The gap between $x^2$ and $x^3$ could be large at first glance but if you think the other way round, for each $y$ you have a range of $x$ bounding $f(y)$, some of which can be arbitrarily close.
Say, I can choose $x = \sqrt{y}-\varepsilon$ or $x = \sqrt[3]{y}+\varepsilon$ then we know $f(\sqrt{y}-\varepsilon)^2 \leq f(y) \leq f(\sqrt[3]{y}+\varepsilon)^3$. When $\varepsilon$ is small enough it actually provides a rigid structure. For what function does $f(x^{1/n})^n \sim f(x)$ holds? It has to be the monomial $x^c$, and we are going to prove it.
It's very hard to work with the given condition, but with some smart transformation we can apply a neat trick. Let $g(x) = \ln f(e^x)$. Then for $2\leq \frac{y}{x} \leq 3$ we have $2\leq \frac{g(y)}{g(x)} \leq 3$ which is a way nicer representation of powers.
The neat trick is to notice that the powers $2^a3^b$ for integer $a,b$ is dense over positive reals. That says, we can turn our idea on ridigity into formal statement.
For positive integers $a,b,c,d$ so that $2^a3^{-b}\leq x \leq 3^c2^{-d}$ we have $g(2^a3^{-b}) \geq 2^a3^{-b}g(1)$ and $g(3^c2^{-d}) \leq 3^c2^{-d}g(1)$. Note that $g$ has positive real domain.
By choosing close enough exponent we can show monotonicity by contradiction, then for any $y$ we can pack $2^a3^{-b}\leq y \leq 3^c2^{-d}$ for positive integers $a,b,c,d$ to force $g(y) = yg(1)$, recovering $f(x) = x^{g(1)}$.
I showed full solution here to appreciate the beauty of Putnam solutions. There is another question I wanted to show (2022 B6) but that is such a beast and has less emphasize over growth rate but that question is definitely worth a check.
4. Sequences
Well...the technique would not be useful if it's solely for a highly artifical genre of problems. I want to show a wider variety of problems where such mindset is actually useful.
Let's start with something simpler.
Example 11. (IMO 2014 P1) Let $a_0 < a_1 < a_2 < ...$ be sequence of increasing positive integers. Prove that there exists unique $n\geq 1$ such that $a_n < n^{-1}(a_0+\ldots+a_n) \leq a_{n+1}$.
There are many different solutions, but let's think it in the growth rate way. Two sequences -- the main sequence $(a_n)$ and the average sequence. It is clear that the main sequence is growing quicker, so we only need to prove the existence of the crossing point.
Define difference term $d_n = a_n-a_{n-1}$, sum $S_n = a_0+\ldots+a_n$ and the difference between the two sequences $\Delta _n = S_n/n-a_n$. The main condition becomes $0<\Delta _n \leq d_{n+1}$ and the recurrence becomes $\Delta _{n+1} = \frac{n}{n+1}(\Delta _n - d_{n+1})$.
Note that this is an increasing sequence of positive integers, meaning $d_n\geq 1$, so $(\Delta _n)$ is destined to cross zero and never turning back. We just need to check two more technicalities: $\Delta _1 >0$ and that once $0<\Delta _n \leq d_n$ the next term $\Delta_{n+1}$ is non-positive, and both are easy.
Example 12. (Putnam 1966 A3) Let $a_1 \in (0,1)$ and define the sequence by $a_{n+1} = a_n(1-a_n)$. Prove that $\lim _{n\to \infty}na_n = 1$.
We are asked to prove that $a_n$ behave like $1/n$, or that $1/a_n$ behaves linearly. This isn't hard as $\frac{1}{a_{n+1}} = \frac{1}{a_n(1-a_n)} = \frac{1}{a_n} + 1 + a_n +...$.
That gives the difference $1/a_{n+1}-1/a_n = 1/(1-a_n)$. From here either you showoff by using Stolz-Cesàro, or use the fact that $a_n\to 0$ to estimate the limit $\lim na_n$.
Example 13. (Putnam 2020 A3) Let $a_0 = \pi/2$ and $a_{n+1} = \sin a_n$. Determine if $\sum a_n^2$ converges.
Note that this is not the usual sin sequence (which would probably be dense) because $\sin x \leq x$ which lead to a decay. What is the growth rate of $a_n$? Should the series $\sum a_n^2$ to just diverge the sensible growth rate is $n^{-1/2}$, which turned out to be the case. We can prove this by the estimation $\sin x \geq x - x^3/6$.
In fact, this order is tight heuristically although the error term isn't exactly $O(n^{-2})$. When $a_{n+1}^2-a_n^2$ doesn't work, what if we try $a_{n+1}^{-2}-a_n^{-2}$? That yields a direct use of a theorem that we already used above...and I leave that as exercise.
Both examples utilizes the reciprocal trick. In a more general heuristic, if we have predicted the rate then we can apply the right transformation where increments is constant which gives a strong characterization or bound.
Mathematically, for $a_{n+1} = a_n - ca_n^p + o(a^p_n)$ for $c>0, p>1$ then the transformation $b_n = a_n^{-(p-1)}$ gives $b_{n+1}-b_n \sim c(p-1)$ and so $a_n \sim (c(p-1)n)^{-1/(p-1)}$.
~~
One great example on question of this type (sequence involving growth rate) would be 2006 B6 which the answer is crystal clear (you just consider the continuous case with difference turned into differential equation). It is so delicate in details, yet much simpler with an answer in mind.
Some may say these sequence type problems are merely discrete functions that are not much different from continuous functions. Let us look at problems that do not associate with a particular function yet the same mindset remains useful.
(Cont.)
No comments:
Post a Comment