Algebra, Inequalities, Polynomials and Functional Equations — IOQM, RMO and INMO

Weightage: Algebra supplies one or two problems in most olympiad papers: an inequality, a polynomial or a functional equation. These problems reward a short list of inequalities used with the equality case in mind, and a disciplined way of extracting information from a functional equation.

1. Always find the equality case first

Every inequality has an equality case, and the proof should be built around it. Guess it, usually the symmetric point such as $a=b=c$, then pick the inequality that is tight there. If your chosen tool is not tight at the equality case, it cannot prove the statement.

2. AM-GM

For non-negative reals:

$\frac{a_1+\cdots +a_n}{n}\ge \sqrt[n]{a_1\cdots a_n}$

with equality only when all terms are equal.

Worked example. Prove $(a+b)(b+c)(c+a)\ge 8abc$ for positive $a,b,c$. Since $a+b\ge 2\sqrt{ab}$ and likewise for the other pairs, the product is at least $8\sqrt{a^2{b}^2{c}^2}=8abc$. Equality holds at $a=b=c$.

Splitting terms to hit the equality case. To minimise $x+4/x^2$ for $x>0$, write it as $\frac{x}{2}+\frac{x}{2}+\frac{4}{x^2}$. The product of the three terms is $1$, so the sum is at least $3$, with equality when $x/2=4/x^2$, which is $x=2$.

3. Cauchy-Schwarz and its forms

$(a_1^2+\cdots +a_n^2)(b_1^2+\cdots +b_n^2)\ge (a_1{b}_1+\cdots +a_n{b}_n{)}^2$

with equality when the vectors are proportional. The Engel form is:

$\frac{x_1^2}{y_1}+\cdots +\frac{x_n^2}{y_n}\ge \frac{(x_1+\cdots +x_n{)}^2}{y_1+\cdots +y_n}$

for positive $y_i$.

Worked example. If $a+b+c=6$, then $3(a^2+b^2+c^2)\ge (a+b+c{)}^2=36$, so $a^2+b^2+c^2\ge 12$, with equality at $a=b=c=2$.

4. Rearrangement, Chebyshev and convexity

The rearrangement inequality says that for two sequences, the sum of products is largest when both are sorted the same way and smallest when sorted oppositely. Jensen's inequality says that for a convex function $f$, $f\left(\frac{x_1+\cdots +x_n}{n}\right)\le \frac{f(x_1)+\cdots +f(x_n)}{n}$. A function with $f^{\prime \prime }\ge 0$ is convex.

Technique: substitution. For a condition such as $abc=1$, substitute $a=x/y$, $b=y/z$, $c=z/x$, or for $a+b+c=1$ use homogenisation to make the inequality uniform in degree.

5. Polynomials

Vieta's formulas for $x^3+p{x}^2+qx+r$ with roots $\alpha ,\beta ,\gamma$: $\alpha +\beta +\gamma =-p$, $\alpha \beta +\beta \gamma +\gamma \alpha =q$, $\alpha \beta \gamma =-r$.

Worked example. For $x^3-6x^2+11x-6$ with roots $\alpha ,\beta ,\gamma$, the sum of squares is $\sum {\alpha }^2=(\sum \alpha {)}^2-2\sum \alpha \beta =36-22=14$. (The roots are $1,2,3$, and $1+4+9=14$.)

Other tools:

• Factor theorem: $(x-a)\mid P(x)$ if and only if $P(a)=0$. The remainder on division by $x-a$ is $P(a)$.
• Rational root theorem: a rational root $p/q$ in lowest terms of an integer polynomial has $p\mid a_0$ and $q\mid a_n$.
• For integer polynomials, $a-b\mid P(a)-P(b)$. This one fact solves many integer-valued polynomial problems.
• Lagrange interpolation: a polynomial of degree at most $n$ is determined by its values at $n+1$ points.

6. Sequences and recurrences

For a linear recurrence $a_{n+2}=p{a}_{n+1}+q{a}_n$, solve the characteristic equation $r^2=pr+q$. Distinct roots $r_1,r_2$ give $a_n=A{r}_1^n+B{r}_2^n$, and a repeated root $r$ gives $(A+Bn)r^n$.

For $a_{n+1}=2a_n+1$ with $a_1=1$, add $1$ to both sides: $a_{n+1}+1=2(a_n+1)$, so $a_n+1=2^n$ and $a_n=2^n-1$. Also look for invariants and telescoping sums such as $\frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1}$.

7. Functional equations

You cannot solve a functional equation by guessing. You must derive the answer and then verify it.

1. Substitute special values: $x=0$, $y=0$, $y=x$, $y=-x$, $y=1$.
2. Test injectivity and surjectivity. If $f(a)=f(b)$ forces $a=b$, then $f$ is injective, and cancelling $f$ from both sides is allowed.
3. Exploit symmetry. Swap the variables and compare.
4. Iterate. Compute $f(f(x))$ and look for an involution or period.
5. Use the Cauchy equation $f(x+y)=f(x)+f(y)$, which gives $f(x)=cx$ on the rationals, and on the reals when $f$ is monotone or bounded on an interval.

Worked example. Suppose $f(x+f(y))=f(x)+y$ for all real $x,y$. Putting $x=0$ gives $f(f(y))=f(0)+y$, so $f$ is injective and surjective.

Putting $y=0$ gives $f(x+f(0))=f(x)$, and injectivity forces $f(0)=0$. Hence $f(f(y))=y$, and replacing $y$ by $f(y)$ in the original gives $f(x+y)=f(x)+f(y)$. The identity $f(x)=x$ satisfies the equation, and any further solution is additive.

Always verify the proposed solution in the original equation, and state the domain.

8. Inequalities in the IOQM

Problems often ask for the maximum or minimum value and the answer is an integer. Find the equality case, apply AM-GM or Cauchy to show the bound, and confirm that the bound is attained. A bound that is never attained is not the answer.

Common traps

• Using AM-GM on a negative number. It needs non-negative terms.
• Missing the equality case. A bound that cannot be attained is not the extremum.
• Cancelling $f$ without injectivity.
• Skipping the verification step in a functional equation.
• Ignoring the domain, such as positive reals versus all reals.

Memory aids

• "Equality first": guess it before choosing the tool.
• "Substitute, inject, symmetrise, iterate": functional equations.
• "$a-b$ divides $P(a)-P(b)$": integer polynomials.

Summary

Inequalities are proved with AM-GM, Cauchy-Schwarz, rearrangement and convexity, always matched to the equality case. Polynomials use Vieta, the factor theorem and divisibility properties, and recurrences use characteristic equations and telescoping.

Functional equations are solved by substitution and by establishing injectivity or surjectivity, then verifying the answer.

Exam protocol

• Write the equality case before any estimate.
• State the domain and check solutions in the original equation.
• For an extremum, show both the bound and that it is attained.
• Do not divide by an expression that might be zero.