Lecture Notes on Mathematical Olympiad Courses

The following sections are included:

• Preface

• Acknowledgments

• Abbreviations and Notations

• Contents

The Mathematical Induction is a very powerful tool for proving infinitely many propositions by using only a few steps. In particular, it can be used often when the propositions are involving the nonnegative integer n.

Definition 17.1. A sequence a₁, a₂, a₃, … is said to be an Arithmetic Progression, which is abbreviated as A.P., if it has a common difference d given by

　　　　 d = a₂ − a₁ = a₃ − a₂ = a_n+1 − a_n, 　 for n = 1,2,3,…

Definition 18.1. A sequence {a_n ∈ ℕ} is said to be a recursive sequence, if starting from some term each term is determined by several of the previous terms, i.e., it can be expressed as a function of several previous terms:

　　　　a_n+m = 𝑓(a_n, a_n+1…, a_n+m−1), 　for n≥n₀.

𝑓 is said to be the recursive formula.

Summation of sequences is a common tool used in each of branches of mathematical olympiad competitions, so there are various methods for evaluating the summation for sequences.

　Besides summations of a partial sum of an A.P., a G.P. and a recursive sequence that we have considered before, in this lecture we will introduce other sequences which appeared in Algebra, Trigonometry, Polynomials, Number Theory and Combinatorics.

　However, thus lecture is not comprehensive. We are not going to mention inequalities of summations and complex numbers and complicated combinatorial identities so that the readers in the senior section level can understand more easily.

Definition 20.1. A set S of integers is said to be a complete residue system modulo m, if every integer is congruent to exactly one integer in S modulo m.

Theorem I. (Chinese Remainder Theorem) If m₁,m₂, ^… , m_k are positive integers with (m_i,m_j) = 1 for any 1 ≤ i < j ≤ k, then the system

x ≡ b₁ 　(mod m₁),　 x ≡ b₂ (mod m₂),  ^…, 　 x ≡ b_k 　(mod m_k) 　(21.1)

must have solutions for any integers b₁, b₂, ^…, b_k, and the solution set is a congruence class modulo m₁m₂^… m_k, that is, the solutions are formed by the numbers

where M_i = m₁ m₂ … m_k/m_i and M^-1_i is the inverse of M_i modulo m_i for i = 1, 2, ^…, k.

In the lecture notes for Junior section we discussed linear and quadratic Diophantine equations. In this lecture we will discuss the general non-linear Diophantine equations.

Although the Diophantine equations x² + y² = z² and x² − Dy² = 1 both are quadratic, they are fundamental in number theory and are commonly used for dealing with many problems in number theory. Hence it is worth making them as the topic of an entire lecture.

The general form of a quadratic congruence equation is

where a ≢ 0 (mod p) and p > 1. When p is an odd prime number and (a, p) = 1, (24.1) is equivalent to

…

Theorem I. (Cauchy-Schwartz Inequality) For any real a₁, a₂, …, a_n and b₁, b₂, …, b_n,

.

Furthermore, if a₁, a₂, …, a_n are not all zeros, the equality holds if and only if there exists a constant k such that b_i = k_ai for all i = 1, 2, …, n.

Theorem I. (Rearrangement Inequality) Let a₁ ≤ a₂ … a_n and b₁ ≤ b₂ ≤ … ≤ b_n be two groups of ordered real numbers. For a permutation (j₁, j₂, …, j_n) of (1, 2, … , n), the sums given by

S_O = a₁b₁ + a₂b₂ + … + a_nb_n, (ordered sum)

S_M = a₁b_j1 + a₂b_j2 + … + a_nb_jn, (mixed sum)

S_R = a₁b_n + a₂b_n−1 + … + a_nb₁, (reverse sum)

must obey the inequalities : S_R ≤ S_M ≤ S_O…

The following sections are included:

• Algebraic Manipulation

• Substitution of Variables or Expressions

• Enlargement and Compression of One side of an Inequality

• Localization of An Inequality

• Mathematical Induction

In this lecture two kinds of methods of counting are introduced:

　(1)  The applications of the three fundamental principles (Addition Principle, Multiplication Principle and Inclusion-Exclusion Principle) and Permutations and Combinations;

　(2)  The applications of the Pairing Method and Correspondence Principle.

In this lecture two kinds of methods of counting are introduced:

　(1) Applications of the Counting in Two Ways method;

　(2) Applications of the Recurrence method.

Definition 30.1. An equation containing one or more unknown functions is called a functional equation, if the operations in the equation are addition, subtraction, multiplication, division and composition operations of the functions only.

The following sections are included:

• Solutions to Testing Questions

• Appendices

• Appendix A Theorem on Second Order Recursive Sequences

• Appendix B Proofs of Theorems On Pell’s Equation

• Appendix C Theorems On Quadratic Residues

• Appendix D Proofs of Some Important Inequalities

• Appendix E Note On Cauchy’s Problem in Functional Equations

• Index