0.1 Techniques and Patterns
One of the many fields in olympiad algebra that has known techniques and patterns that could come very handy would be inequality. This section mostly includes the techniques that can be implemented with simple pattern recognition, and shares some of my personal experience that I built from solving inequality problems.
0.1.1 Telescoping
Telescoping series and generalization powered with classic inequalities like AM-GM and Cauchy Schwarz can really come handy in solving some problems.
Definition 0.1.1
Telescoping series refers to a substantially large series that cancels out to leave only the beginning and the ending terms.
The definition above is not “formal” per se, but an example of such series would be the following. \begin{align*} \sum _{k=1}^n (a_k - a_{k+1}) &= a_1 - a_2 + a_2 - a_3 + a_4 - a_5 + \cdots + a_n - a_{n+1} \\ &= a_1 - a_{n+1} \end{align*}
Of course telescoping series do not reveal themselves in problems easily. A common form in which they are found is fraction. For instance, the following sequence telescopes. \begin{align*} \sum _{k=1}^n \left ( \frac {1}{k(k + 1)} \right ) &= \sum _{k=1}^n \left ( \frac {1}{k} - \frac {1}{k + 1} \right ) \\ &= \frac {1}{1} - \frac {1}{2} + \frac {1}{2} - \frac {1}{3} + \cdots + \frac {1}{n} - \frac {1}{n + 1} \\ &= 1 - \frac {1}{n + 1} = \frac {n}{n + 1} \end{align*}
Below is another classic problem with an interesting property.
Exercise 0.1.2
Show that the following inequality holds. \[ \sum _{i = 1}^n \frac {1}{i^2} < 2 \]
Proof.
Consider the identity \(\frac {1}{k(k + 1)} = \frac {1}{k} - \frac {1}{k + 1}\) for \(k \neq 0, -1\). Expanding, the following inequalities are obtained. \begin{align*} \frac {1}{1^2} + \frac {1}{2^2} + \cdots + \frac {1}{n^2} &< 1 + \frac {1}{1 \cdot 2} + \cdots + \frac {1}{(n - 1) \cdot n} \\ &= 1 + \left ( \frac {1}{1} - \frac {1}{2} \right ) + \cdots + \left ( \frac {1}{n - 1} - \frac {1}{n} \right ) \\ &= 2 - \frac {1}{n} < 2 \end{align*}
Therefore, the inequality holds.
With the idea in mind, let’s solve a problem to see how they can be powered with fundamental inequalities to solve problems.
Exercise 0.1.3: 2007 Belarusian MO Final Problem 2 (\(\bullet \circ \circ \))
Show that the following inequality holds for all \(a_1, \ldots , a_{n+1} > 0\). \[ \frac {1}{a_1} + \frac {a_1}{a_2} + \frac {a_1 a_2}{a_3} + \cdots + \frac {a_1 a_2 \cdots a_n}{a_{n+1}} \geq 4(1 - a_1 \cdots a_{n+1}) \]
Solution.
Before applying any techniques or inequalities, let’s first analyze the inequality. Notice that in our left hand side of the inequality, we have products \(a_1 \cdots a_k\) that grows after each term. On our right hand side, we have the product \(a_1 \cdots a_{n+1}\). Now letting \(p_k = a_1 \cdots a_k\) and \(p_0 = 1\), we can see that our right hand side becomes \(4(p_0 - p_{n+1})\), which hints that the sequence telescopes. Indeed, consider the following expansion. \begin{align*} 4(1 - a_1 \cdots a_{n+1}) &= 4 \left \{ (1 - a_1) + (a_1 - a_1 a_2) + \cdots \right . \\ &\qquad \qquad \qquad \qquad \quad +\left . (a_1 \cdots a_{n} - a_1 \cdots a_{n+1}) \right \} \end{align*}
Matching each expanded term with the terms in left hand side, it suffices to show that \[ \frac {a_1 \cdots a_k}{a_{k+1}} \geq 4(a_1 \cdots a_k - a_1 \cdots a_{k+1}) \] holds. Rearranging the terms the following inequality hold. \[ \frac {a_1^2 a_2^2 \cdots a_k^2}{a_1^2 a_2^2 \cdots a_{k+1}^2} + 4 a_1 \cdots a_{k+1} \geq 4 a_1 \cdots a_k \] Because \(a_k > 0\) by definition, the inequality holds by AM-GM inequality.
The problem above uses the property of telescoping series and AM-GM inequality for a proof. If you see such form, it would be worth suspecting that we can use telescoping technique.
* Homogenization, Normalization * Substitution, uvw method, Ravi Transformation * Fudging, Smoothing, and Ordering * Super-Sums of Square-Weights (SOS) * Majorization Theory * Mixing Variables * Isoperimetric Inequalities