Capturing growth rate in problem solving (2): functions and sequences

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

Capturing growth rate in problem solving (1): motivation

This is a sketch of seminar I will deliver to undergraduate problem solvers, and I feel like this is a good chance to fill more advanced math content into my blog. I like going deep in small concepts, but bigger projects like this also brings much fun.

I will split into three parts as follows.

I. Motivation

II. Contest problems

III. More problems and generalization

Enjoy :)

*

1. Introduction

Why growth rate? We start with a very simple example.

Example 1. Consider the limit $\lim _{x\to \infty}\frac{2x^2-3x-2}{x^2+7x+100} = 2$.

Before the access to the $\varepsilon - \delta$ approach, students are taught to bound the function by simpler fractions with clear limit then apply squeezing. It's a torturing analytical workout and students often get lost in the process. 

Everyone knows clearly the answer is $2/1 = 2$, the problem is how do we reach there. Then we ask the question: why is that clear in the first place?

The answer is the order -- both are of order $x^2$. Once we divide by the order we have the limit

$\frac{2+o(1)}{1+o(1)} \to \frac{2}{1} = 2$.

The essence is to identify the order work around it. And the important takeaway of the seminar as to be laid below -- is to show that such thinking is widely applicable, far more than simple real analysis exercise.

To this end, let us recall a simple but important lemma, the polynomial dominance:

Lemma 1. Suppose $f(x), g(x)$ are polynomials of order $m,n$ with $m>n$, then there exists $L>0$ such that $|f(x)|>|g(x)|$ for all $|x|>L$. Call $f$ dominates $g$ (over applicable domain).

Proof. Exercise(!).

Every polynomial order is a distinct growth rate with a strict order. Actually the same applies to non-integer power although that is not our main focus today.

Think about a smooth function $f \in \mathbb{R}$. For each point $x\in \mathbb{R}$ we have a converging Taylor expansion $f(c) = \sum a_{n,c}(x-c)^n$ then we know $f(x)\approx a_m(x-c)^m$ around $x=c$ where $a_m$ is the lowest non-zero coefficient. The same applies when you look into the complex space where the poles and zeros are decided by the leading terms (both in positive negative powers) in the Laurent series.

Of course, one may extend the complex plane to the Riemann sphere (or by projective geometry in words of some geometers), one my find that infinity and behavior at infinity is merely zeros and poles at another point!

There are for sure more growth order than just polynomial. Exponential and log grwoth are the most typical one. Their growth rate is characterized by whatever quicker and slower than polynomial. 

Lemma 2. Let $a>1$. Then the exponential function $a^x$ dominates any polynomial and the log function $\log _a x$ is dominated by any (non-constant) polynomial over $x >0$.

Exponential curve is even more common in branches of mathematics, in particular on anything involving time. Since exponential functions of larger base also dominates that of lower base -- we actually get to know the growth rate by bounding such function.

Suppose we have an (eventually) increasing function on our hand. The growth rate has to be one of those -- log, polynomial, exponential (of course, sub-log and hyperexponential as well), and these growth rates are mutually exclusive. Then within the same category each subclasses -- bases of exponentials or order of polynomials (well logs of different bases are constant multiples of each other) -- are mutually exclusive in the sense that one always dominates another and forms a total order in it. Knowing the growth rate pretty much locks the behavior, and in some problems the functions themselves.

The aim of the seminar, is to appreciate how common growth order becomes a crucial piece of information that can be used, or acts as a motivation towards the solution of a problem. 

To start with, we lay down even more examples where undergraduate results uses growth rate as a centerpiece of the argument.

2. Classic examples

Let us look at some relatively accessible examples. We emphasize that the growth rate often provide crucial information.

First, we look at more results in complex analysis.

Example 2. (Liouville) Suppose $f$ is an entire function with $|f(z)|\leq M|z|^k$ for some $M>0$ and non-negative integer $k$, then $f$ is a polynomial of degree at most $k$.

Proof. Cauchy's integral formula.

In other words, any non-polynomial entire function admits a path $\gamma$ such that $|f(\gamma(t))|$ is not bounded by polynomials.

Example 3. (Rouché) Let $f,g$ be holomorphic over closed region $K$. If $|f(z)|>|g(z)|$ for all $z\in \partial K$ then $f$ and $f+g$ has equal number of zeros in $K$.

Proof. Argument principle. Note that it also extends to poles counting (!).

The inequality $|f(z)|>|g(z)|$ does not necessarily means $g$ is dominated by $f$ even just over $K$ but classic examples involve a higher degree polynomial and a lower degree polynomial, showing how the dominating term dictates the behavior of the function.

Example 4. (Ergodic Markov chain) Denote the correspondant matrix of the chain $A$, then $A$ has eigenvalue $\lambda _1 = 1 \geq |\lambda _2| \geq |\lambda _3|\ldots$. Furthermore, the error term (the $L_{\infty}$ distance) from the terminal state $v_{\infty}$ has decay rate dominated by the second eigenvalue. More precisely for $v_k$ the $k$-th state vector satisfies $\| v_k-v_{\infty}\|_{\infty} = O(|\lambda _2|^k)$.

Proof. Perron-Frobenius. This second eigenvalue characterization is quite widely used in fields like harmonic analysis. Note that we implicitly infer the chain to be finite reversible so that we don't run into non-trivial Jordan blocks.

Example 5. (Liouville approximation) If $x$ is an irrational algebraic number of order $n$ then there exists constant $c_x>0$ such that $|x-\frac{p}{q}| > c_xq^{-n}$ for all integers $p,q$ with $q>0$.

Proof. Elementary number theory. I feel like I have been applying tricks avoiding proofs too much here. Perhaps left as exercise.

This time, the function or concern is the approximability -- we don't necessarily need a continuous function to talk about growth rate. The result basically says approximability is bounded below be the decaying factor $q^{-n}$.

We conclude our introduction with a heavyweight classic.

Example 6. (PNT) $\pi (x) \sim x/\ln x$.

Proof. By wikipedia...joking but seriously the analysis details are so delicate despite the simple idea.

This result is not proving by capturing the growth rate. Instead, the result itself is about growth rate and it becomes the pillar of analytical number theory, one among the most important branch in modern mathematics. Much of the problems here starts from a counting function that turns out to be much, much more fundamental...like the Riemann hypothesis which is also a growth rate problem in nature.

But don't worry, we are not here trying to prove anything big. We just demonstrated how common such concept is, and we try to equip such mindset to facilitate problem solving.

(Cont.)