60-odd years of moscow mathematical

BC makes sense.
[a, b) denotes the set of real numbers x such that a ≤ x < b; we similarly define [a, b], (a, b), etc. We
sometimes write ]a, b[ for (a, b), ]a, b] for (a, b], etc. Observe that either of a and b here might be equal to
−∞ or ∞.
[x] denotes the integer part of x, i.e., the greater integer that does not exceed x, e.g. [5] = 5,
£
1
1
2
¤
= 1,
[3/4] = 0, [3/2] = 1, [π] = 3, [−1.5] = −2, etc.
{x} = x − [x] denotes the fractional part of x.
n! = 1 · 2 · 3 · . . . · (n − 1) · n; this reads factorial (of) n. Clearly, 1! = 1; we convene that 0! = 1.
(2n)!! = 2 · 4 · 6 · . . . · (2n − 2) · 2n denotes the product of n consecutive even numbers (reads semi-factorial
of 2n).
(2n − 1)!! = 1 · 3 · 5 · . . . · (2n − 3) · (2n − 1) denotes the product of n consecutive odd numbers (reads
semi-factorial of 2n − 1).
Clearly, (2n)!! · (2n − 1)!! = (2n)!
The inverse functions sin
−1
, cos
−1
, etc. were denoted in the USSR and in many older books by arcsin,
arccos, etc. The oldfashioned notation has an advantage: no chance to confuse (except by accident) the
value of the inverse function at a point with the reciprocal of the value of the function, e.g., generally,
arcsin(x) 6= (sin(x))
−1
.
Recall that
x = arcsin y ⇐⇒ |y| ≤ 1, |x| ≤
π
2
; y = sin x
z = arccos t ⇐⇒ |t| ≤ 1, |z| ∈ [0, π]; t = cos z.
lg x stands for log
10
x and ln x or log x for the natural logarithm with base
e = lim
n→∞
µ
1 +
1
n
¶
n
= 2.71828 . . . .
A periodic decimal fraction is usually abbreviated to
a
n
. . . a
1
a
0
.a
−1
. . . a
−m
(a
−m−1
. . . a
−m−t
),
where the digits in parentheses constitute the least period (of length t).
a
−n
= 1
a
n
for a positive integer n.
Two numbers a and b are called incommensurable if
a
b
6∈
Q
.
Facts from algebra. An integer a is said to be divisible by an integer b if a = bc for some integer c;
in this case a is a multiple of b (and c) and b is a divisor of a; this is sometimes denoted as a
..
. b or b | a, e.g.
a
..
. 2 if and only if a is an even number. A proper divisor of a is an integer divisor b such that 1 < b < |a|. A
prime number is an integer p > 1 without proper divisors.
Let a and b be positive integers; we denote by GCD(a, b) or just (a, b) for brevity their greatest common
divisor, i.e., the maximal positive integer c such that both a and b are divisible by c. We denote by LCM (a, b)
their least common multiple, the least positive integer divisible by both a and b. The following property of
GCD and LCM is often used to calculate LCM : GCD(a, b) × LCM (a, b) = ab.
The above definition of GCD(a, b) can be used to define GCD(a, b) for a, b ∈
Z
when b 6= 0; the above
definition of LCM (a, b) fits any nonzero integers; these generalized notions satisfy
GCD(a, b) × LCM (a, b) = |ab|.
Numbers a and b such that (a, b) = 1 are called relatively prime or coprime if GCD(a, b) = 1; if a and b
are relatively prime then ac
..
. b implies c
..
. b.
* * *
We use divisibility theorems to prove by the rule of contraries the existence of irrational numbers, e.g.,
√
2,
√
3 are irrational. (The same idea applies to
√
q and
√
pq for prime p, q.)
The fundamental theorem of arithmetic. Every integer n > 1 is the product of its prime divisors
defined uniquely up to a permutation. In particular, if p
1
< p
2
< . . . < p
s
are all divisors of an integer n,
then the representation
n = p
k
1
1
p
k
2
2
. . . p
k
s
s
, where k
1
, . . . , k
s
∈
Z
+
,
always exists and is unique.

---

PREREQUISITES AND NOTATIONAL CONVENTIONS
15
An integer a is said to be divisible by a nonzero integer b with remainder r if
a = bq + r for some integers q and r,
0 ≤ r < |b|.
We sometimes use the notation r = r(a) for a given b. For a fixed b the possible values of r(a) are 0, 1,
. . . , b − 1 and are called residues modulo b. Two numbers x and y are congruent modulo m if (x − y)
..
. m.
We write x ≡ y (mod m).
It is easy to demonstrate that if a ≡ b (mod n) and c ≡ d (mod n) then a + c ≡ b + d (mod n) and
ac ≡ bd (mod n).
Similarly, given polynomials f (x) = a
n
x
n
+ a
n−1
x
n−1
+ · · · + a
1
x + a
0
and g(x) = b
m
x
m
+ b
m−1
x
m−1
+
· · · + b
1
x + b
0
, we say that f (x) is divisible by g(x) if f (x) = g(x)q(x) for some polynomial q(x).
Recall, that the degree of a polynomial f (x) = a
n
x
n
+ a
n−1
x
n−1
+ · · · + a
1
x + a
0
is the greatest power
of its nonzero monomial; we write deg f (x) = n. If g(x) 6= 0 it is always possible to uniquely represent f (x)
in the form
f (x) = g(x)q(x) + r(x),
where deg r(x) < deg g(x).
The above formula implies
Bezout’ theorem: For any number x
0
a polynomial f (x) can be represented in the form
f (x) = q(x)(x − x
0
) + r(x),
where q(x) is a polynomial.
Proof. In the displayed formula take g(x) = x − x
0
, deg r(x) < deg(x − x
0
) = 1; hence, r(x) is a
constant fumction: r(x) = r(x
0
), as was required. Q.E.D.
If f (x
0
) = 0, then x
0
is a root or a zero of the polynomial f ; this is true if and only if f is divisible by
x − x
0
.
The fundamental theorem of algebra. Every nonconstant polynomial f (x) with complex coefficients
has (deg f ) complex roots.
Inequalities. Cauchy’s inequality
1
a
1
+ a
2
+ . . . + a
n
n
≥
n
√
a
1
. . . a
n
for a
1
≥ 0, a
2
≥ 0, . . . , a
n
≥ 0
relates the arithmetic mean (the lhs) and the geometric mean (the rhs). One can prove it by induction
(rather tedeous job). A particular case is the relation (prove it!):
a
1
+ a
2
2
≥
√
a
1
· a
2
≥
2
1
a
1
+
1
a
2
,
where the last term is the harmonic mean.
Though we will not use it in this book, it is too tempting not to mention here the following fact (prove it yourself). Denote
by S
p
(a, b) =
“
a
p
+ b
p
2
”
1
p
for any non-negative real a, b and p 6= 0 the p-th order mean of a and b. On Fig. 1 the following
proposition is illustrated:
If a < b then a ≤ S
p
(a, b) ≤ S
q
(a, b) ≤ b for any p ≤ q.
Figure 1. (N1)
Figure 2. (N2)
The means of order p and −p are related: S
p
(a, b)S
−p
(a, b) = ab. One can prove (do it!) that lim
n→∞
S
1
n
(a, b) =
√
ab and,
therefore, it is natural to define S
0
(a, b) as
√
ab.
Progressions. An arithmetic progression is a sequence {x
n
, where n ∈
N
} in which x
n
= x
n−1
+ d.
Hence, x
n
= x
0
+ nd.
Example. The progression x
n
= n (hence, d = 1) is often referred to as the natural series.
1
Sometimes called Schwarz’ inequality in Germany and Bounyakovsky’s inequality in Russia.

---

16
INTRODUCTION
For an arithmetic progression {x
n
}
n∈
N
we have (add x
0
+ ... + x
n
with x
n
+ ... + x
0
term-wise):
n
X
k=0
x
k
=
x
0
+ x
n
2
(n + 1).
A geometric progression is a sequence of nonzero terms {x
n
}
n∈
N
in which x
n
= x
n−1
q. Hence, x
n
=
q
n
· x
0
. An example: x
n
= q
n
. For a geometric progression {x
n
}
n∈
N
with q 6= 1 we have:
n
X
k=0
x
k
= x
0
1 − q
n+1
1 − q
.
If |q| < 1, then |q
n
| tends to 0 as n → ∞; hence, we can define the infinite sum of all terms of the geometric
progression to be
∞
P
k=0
x
k
= x
0
1
1 − q
.
A Fibonacci sequence is a sequence {x
n
}
n∈
N
in which x
n
= x
n−1
+ x
n−2
. Sometimes n is allowed to
run over
Z
. Most often we encounter the sequence with x
0
= 0, x
1
= 1, i.e.,
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . .
The rule of sum and the rule of product. Let A and B be finite sets, n ≥ 1 and m ≥ 1 be their
cardinalities, respectively.
S) If A and B have no common elements then there are exactly n + m elements contained in the union
of these sets.
P) There are exactly nm ordered pairs (a, b) with a ∈ A, b ∈ B.
The rule of product enables one to calculate C
k
n
— the number of ways to choose k elements from n
given (indistinguishable) ones. The answer: C
k
n
=
n!
k!(n−k)!
. Another common notation for this number is
¡
n
k
¢
, reads: n choose k.
For any numbers a, b and a nonnegative integer n we have the binomial formula:
(a + b)
n
=
n
X
k=0
C
k
n
a
k
b
n−k
.
Observe that C
k
n
= C
n−k
n
and deduce important identities:
n
P
k=0
C
k
n
= (1 + 1)
n
= 2
n
and
n
P
k=0
(−1)
n
C
k
n
= 0.
Vi`
eta’s theorem. The roots x
1
, x
2
of a quadratic equation ax
2
+ bx + c = 0 satisfy the following
relations: x
1
+ x
2
= −b, x
1
· x
2
= c.
Facts from geometry. A midline of a triangle (the midline of a trapezoid) is the line segment con-
necting midpoints of two sides of the triangle (trapezoid). The midline’s characteristic property (prove it!):