Note 1
Prerequisites

Before getting into actual contents, I wanted to briefly review some of the topics that we learn in competitions because many of the olympiad topics builds from similar intuitions. This note includes basic definitions and notations that would be used throughout the notes and some concepts that must be covered before expanding them later in the notes.

1.1 Definitions and Notations

Let’s first get started with definitions for different means.

For weighted means, we can do the same as we would normally do with \(w_i \geq 0\). \[ M_w^p \coloneqq \left ( \frac { \sum _{k=1}^n w_k a_k^p }{ \sum _{k=1}^n w_k } \right )^\frac {1}{p} \] Note that the definition above is for generalized mean. Meaning, depending on the values of \(p\), we can derive some of more familiar means.

First, let’s substitute \(p = 1\) to begin with arithmetic mean. \[ M_1 = \left ( \frac { \sum _{k=1}^n a_k }{n} \right ) \] This is arithmetic mean, the mean that we are all familiar with! Using the weighted generalized mean, we can get the formula for weighted arithmetic mean. \[ M_w^1 = \left ( \frac { \sum _{k=1}^n w_k a_k }{ \sum _{k=1}^n w_k } \right ) \] Similarly, we can obtain quadratic mean by substituting \(p = 2\). \[ M_2 = \sqrt { \frac {\sum _{k=1}^n a_k^2}{n} } \] Deriving geometric mean is quite different because \(p = 0\) gives us \(\frac {1}{0}\) in the exponent, which is undefined. Therefore by convention, we define geometric mean with \(M_0 (a_1, \dots , a_n) \equiv \lim _{p \to 0} M_p (a_1, \dots , a_n)\). Substituting, we obtain the following equations. \begin{align*} M_0 &= \lim _{p \to 0} \left ( \frac {\sum _{k=1}^n a_k^p}{n} \right )^\frac {1}{p} \\ \ln (M_0) &= \ln \left ( \lim _{p \to 0} \left ( \frac {\sum _{k=1}^n a_k^p}{n} \right )^\frac {1}{p} \right ) = \lim _{p \to 0} \frac { \ln \left ( \frac {1}{n} \sum _{k=1}^n a_k^p \right ) }{p} \end{align*}

Therefore using L’Hôpital’s rule, \[ \ln (M_0) = \lim _{p \to 0} \frac { \frac {1}{n} \sum _{k=1}^n a_k^p \ln (a_k) }{ \frac {1}{n} \sum _{k=1}^n a_k^p } = \frac {1}{n} \sum _{k=1}^n \ln (a_k) = \ln \left ( \prod _{k=1}^n a_k \right )^\frac {1}{n} \] is obtained. Rewriting the equation, the familiar version of the geometric mean formula is obtained. \[ M_0 = \left ( \prod _{k=1}^n a_k \right )^\frac {1}{n} = \prod _{k=1}^n a_k^\frac {1}{n} = \sqrt [n]{a_1 a_2 \cdots a_{n-1} a_n} \] Continuing, we can obtain harmonic mean with \(p = -1\). \[ M_{-1} = \left ( \frac {\sum _{k=1}^n a_k^{-1}}{n} \right )^\frac {1}{-1} = \frac {n}{ \sum _{k=1}^n \frac {1}{a_k} } \] Lastly for unbounded \(p\), we define \(M_{-\infty }\) and \(M_\infty \) as the following by convention. \begin{align*} M_{-\infty } (a_1, \dots , a_n) &\equiv \lim _{p \to -\infty } M_p (a_1, \dots , a_n) = \min (a_1, \dots , a_n) \\ M_{\infty }(a_1, \dots , a_n) &\equiv \lim _{p \to \infty } M_p (a_1, \dots , a_n) = \max (a_1, \dots , a_n) \end{align*}

Continuing, here is another very important definition for sequences.

We will see more on majorization when we discuss inequalities. Continuing, let’s discuss some common notations.

Below are very common sum notations that will be used throughout the notes. They are very common in olympiads, and is worth noting even if you are not seriously studying for olympiads.

You will most likely see this notation with three variables, and we can also specify with variables we are going to cycle. \[ \sum _{x,y,z} \frac {xw}{yz} = \frac {xw}{yz} + \frac {yw}{zx} + \frac {zw}{xy} \] As we have for cyclic sum, we also have notation for symmetric sums.

Notice that permutation of variables does not affect the value for a symmetric function \(f(s_1, s_2, \ldots , s_n)\). Therefore, \[ \sum _\text {sym} f(s_1, s_2, \ldots , s_n) = n! f(s_1, s_2, \ldots , s_n) \] holds for such functions.

These are the introduction to basic definition and notations! For our next section, let’s review some of the topics that we learn from competitions.