Sequen es

1
1.1 Preliminaries

1.1.1 Linear Equations

The standard form of a linear equation in variable x is

ax + b = 0 (a 6= 0).

It has a unique solution x = −b/a.

Example 1.1.1. Solve 3x + 4 = −5x + 2.

Answer: x = −1/4.

The graph of the linear function y = ax + b (a 6= 0) is a straight line in the x y-plane, which
intersects the x-axis at x0 = −b/a.
y y
y = ax + b
a>0 a<0

x0 x0
b b

O x O x

y = ax + b

If a > 0, then

(i) ax + b > 0 ⇔ x > x0 ; (ii) ax + b ≥ 0 ⇔ x ≥ x0 ;

(iii) ax + b < 0 ⇔ x < x0 ; (iv) ax + b ≤ 0 ⇔ x ≤ x0 .

If a < 0, then

1
CHAPTER 1. SEQUENCES 2

(i) ax + b > 0 ⇔ x < x0 ; (ii) ax + b ≥ 0 ⇔ x ≤ x0 ;

(iii) ax + b < 0 ⇔ x > x0 ; (iv) ax + b ≤ 0 ⇔ x ≥ x0 .

A linear system of two linear equations in two variables x, y is of the form

(
ax + by = α,
cx + d y = β.

If ad − bc 6= 0, then this system has a unique solution

d α − bβ aβ − cα
x= and y= .
ad − bc ad − bc

Each linear equation in variables x, y represents a straight line in the x y-plane. So solving linear
system in x, y is equivalent to finding the intersection points of lines.

Example 1.1.2. Solve the following linear system:

(
2x − y = 1,
x + 2y = 6.

y
3 2x − y = 1
b
2
x + 2y = 6
1
x
O 1 2 3 4 5 6 7
−1

Answer: x = 8/5, y = 11/5.

1.1.2 Quadratic Equation

The standard form of a quadratic equation is

ax 2 + bx + c = 0 (a 6= 0).

Its solutions are given by

p
−b ± b 2 − 4ac
x= .
2a
The number ∆ = b 2 − 4ac is called the discriminant of the quadratic equation.

(a) If ∆ > 0, the quadratic equation has two distinct real solutions.
CHAPTER 1. SEQUENCES 3

(b) If ∆ = 0, the quadratic equation has one repeated solution.

(c) If ∆ < 0, the quadratic equation has no real solution.

Example 1.1.3. Solve the following quadratic equations.

(a) 2x 2 + x − 1 = 0; (b) 2x 2 − 4x + 2 = 0; (c) 2x 2 − 4x + 7 = 0.

Answer: (a) x1 = −1, x2 = 1/2; (b) x1 = x2 = 1; (c) no real solution.

The graph of the quadratic function y = ax 2 + bx + c (a > 0) is a parabola on the x y-plane.

y y y
∆ > 0 (a > 0) ∆ = 0 (a > 0) ∆ < 0 (a > 0)

b b

O x1 x2 x
b

O x0 x

O x

(a) If ∆ > 0, then y = 0 has two real solutions x1 < x2 .

(i) ax 2 + bx + c > 0 ⇔ x < x1 or x > x2 ; (ii) ax 2 + bx + c ≥ 0 ⇔ x ≤ x1 or x ≥ x2 ;

(iii) ax 2 + bx + c < 0 ⇔ x1 < x < x2 ; (iv) ax 2 + bx + c ≤ 0 ⇔ x1 ≤ x ≤ x2 .

(b) If ∆ = 0, then y = 0 has a repeated real solution x0 .

(i) ax 2 + bx + c > 0 ⇔ x 6= x0 ; (ii) ax 2 + bx + c ≥ 0 ⇔ x ∈ R;

(iii) ax 2 + bx + c < 0 ⇔ no real solution; (iv) ax 2 + bx + c ≤ 0 ⇔ x = x0 .

(c) If ∆ < 0, then y = 0 has no real solution.

(i) ax 2 + bx + c > 0 ⇔ x ∈ R; (ii) ax 2 + bx + c ≥ 0 ⇔ x ∈ R;

(iii) ax 2 + bx + c < 0 ⇔ no real solution; (iv) ax 2 + bx + c ≤ 0 ⇔ no real solution.

The case a < 0 is left as an exercise.

1.1.3 Transcendental Functions

Exponential functions

Let a > 0 (a 6= 1). Then y = a x is called the exponential function of base a.

The function y = a x is defined on R. Its graph lies above the x-axis, and intersects the y-axis
at y = 1. If a > 1, the function is increasing; if 0 < a < 1, the function is decreasing.
CHAPTER 1. SEQUENCES 4

y y
y = 5x y = 4x y = 0.25x x
y = 0.2

y = 2x y = 0.5x

1 1

O x O x

The constant e = 2.71828182845904523536 · · · · ≈ 2.718 is called the Euler number.

Properties 1.1.4 (Exponential Functions). For any a > 0, b > 0 and x, y ∈ R,

(i) a −x = 1/a x ; (ii) a x · a y = a x+y ;

(iii) a x · b x = (ab)x ; (iv) (a x ) y = a x y .

Logarithmic functions

Let a > 0 (a 6= 1). Then y = loga x is called the logarithmic function of base a. The graph of
y = loga x and the graph of y = a x are symmetric with respect to the line y = x.
The function y = loga x is defined for x > 0, and the range of y is R. The graph intersects the
x-axis at x = 1. If a > 1, the function is increasing; if 0 < a < 1, the function is decreasing.

y y
y = 2x

y = log2 x
1
1
y = 0.5x
O O
1 x 1 x

y = log0.5 x

The natural logarithmic function is y = loge x, denoted by y = ln x. The common logarith-

mic function is y = log10 x, denoted by y = lg x.

Properties 1.1.5 (Logarithmic Functions). Let a > 0, b > 0 (a 6= 1, b 6= 1), x > 0, y > 0 and r ∈ R.

(i) loga x + loga y = loga (x y); (ii) loga (x r ) = r loga x;

(iii) loga x = logb x/ logb a; (iv) loga b = r ⇔ a r = b (ln b = r ⇔ b = e r );
(v) loga (a r ) = r ; (vi) a loga x = x.
CHAPTER 1. SEQUENCES 5

Trigonometric functions

The trigonometric functions are the ratios of the sides of a right-angled triangle.

c
b

θ
a

(i) sin θ = b/c; (ii) cos θ = a/c;

(iii) tan θ = b/a = sin θ/ cos θ; (iv) cot θ = a/b = cos θ/ sin θ = 1/ tanθ;
(v) sec θ = c/a = 1/ cosθ; (vi) csc θ = c/b = 1/ sin θ.

The angle can be measured in radian: π(radian) = 180◦ .

θ (degree) 0◦ 30◦ 45◦ 60◦ 90◦

π π π π
θ (radian) 0 6 4 3 2
p p
1 2 3
sin θ 0 2 2 2
1
p p
3 2 1
cos θ 1 2 2 2
0
p p
3
tanθ 0 3
1 3 −
p p
3
cot θ − 3 1 3
0
p p
2 3
sec θ 1 3
2 2 −
p p
2 3
csc θ − 2 2 3
1

The trigonometric functions can be defined periodically on real numbers:

y = tan x

y = sin x y = cos x

x
O
CHAPTER 1. SEQUENCES 6

(i) sin(θ + 2π) = sin θ; sin(θ + π) = − sin θ; sin(−θ) = − sin θ; sin(π − θ) = sin θ;
(ii) cos(θ + 2π) = cos θ; cos(θ + π) = − cos θ; cos(−θ) = cos θ; cos(π − θ) = − cos θ;
(iii) tan(θ + 2π) = tan θ; tan(θ + π) = tan θ; tan(−θ) = − tanθ; tan(π − θ) = − tan θ;

Properties 1.1.6 (Trigonometric Functions).

(i) Co-function identities:

sin(π/2 − α) = cos α; cos(π/2 − α) = sin α; tan(π/2 − α) = cot α; cot(π/2 − α) = tan α.

(ii) Pythagorean identities:

sin2 α + cos2 α = 1; sec2 α − tan2 α = 1; csc2 α − cot2 α = 1.

(iii) Double-angle formulas:

sin(2α) = 2 sinα cos α; cos(2α) = cos2 α − sin2 α = 1 − 2 sin2 α = 2 cos2 α − 1.

(iv) Angle sum and difference identities:

sin(α ± β) = sin α cos β ± cos α sin β; cos(α ± β) = cos α cos β ∓ sin α sinβ.

(v) Sum to product identities:

sin α ± sin β = 2 sin[(α ± β)/2] cos[(α ∓ β)/2];
cos α+cosβ = 2 cos[(α+β)/2] cos[(α−β)/2]; cos α−cosβ = −2 sin[(α+β)/2] sin[(α−β)/2].

(vi) Product to sum identities:

2 sinα cos β = sin(α + β) + sin(α − β); 2 cos α sin β = sin(α + β) − sin(α − β);
2 cosα cos β = cos(α + β) + cos(α − β); 2 sin α sin β = cos(α − β) − cos(α + β).

Theorem 1.1.7 (Area Formula for Triangle). Let a, b be two sides of a triangle, and θ be the
interior angle between a and b. Then the area of the triangle is

A = 21 ab sin θ.

Theorem 1.1.8 (Law of Cosine). Let a, b, c be the three sides of a triangle, and θ be the interior
angle between a and b. Then
c 2 = a 2 + b 2 − 2ab cos θ.

a c

θ b
CHAPTER 1. SEQUENCES 7

1.2 Sequences

1.2.1 Definition of Sequences

A sequence is a list of numbers in definite order:

a1 , a2 , a3 , . . . , an , . . . ,

where an is the nth term of the sequence. It is denoted by {an }∞

n=1 or simply {a n }.

Example 1.2.1. Find the n th term of the following sequence:

1, 9, 25, 49, 81, . . ..

Solution. The n th term is the square of the n th odd positive integer.

a 1 = 12 ,
a2 = (1 + 2)2
a3 = (1 + 2 × 2)2
a4 = (1 + 2 × 3)2
··· = ············
an = [1 + 2 × (n − 1)]2 = (2n − 1)2 .

1.2.2 Arithmetic Sequences

Definition of arithmetic sequence

A sequence {an } is called an arithmetic sequence with common difference d if the difference
of any two consecutive terms is d :

d = an+1 − an , n = 1, 2, 3, . . ..

Let a be the 1st term and d be the common difference of an arithmetic sequence {an }. Then

an = a + (n − 1)d .

More generally,
an = am + (n − m)d .

Example 1.2.2. Given an arithmetic sequence such that (i) the 5th term is 21, and (ii) the sum
of the 3rd and 4th terms is 30. Find the 8th term of the arithmetic sequence.
CHAPTER 1. SEQUENCES 8

Solution. Let an be the n th term of the arithmetic sequence. If a is the 1st term and d is the
common difference, then

a5 = a + 4d = 21 and a3 + a4 = (a + 2d ) + (a + 3d ) = 2a + 5d = 30.

Solve the linear system in a and d :

a + 4d = 21 and 2a + 5d = 30

to get a = 5 and d = 4. Then a8 = a + 7d = 5 + 7 × 4 = 33.

Example 1.2.3. Find the first positive number of the following arithmetic sequence:

−217, −213, −209, . . . .

Solution. The 1st term of the arithmetic sequence a = −217 and the common difference d =
(−213) − (−217) = 4. Then the n th term of the arithmetic sequence is given by

an = a + (n − 1)d = −217 + (n − 1)4.

Hence,
an > 0 ⇔ −217 + (n − 1)4 > 0 ⇔ 4n − 221 > 0 ⇔ n > 221/4 = 55.25.
The index n is an integer; so the smallest possible n is 56, and the first positive number of the
sequence is
a56 = a + 55d = −217 + 55 × 4 = 3.

Sum of arithmetic sequences

We often use Sigma notation for the sum:

n
X
ai = am + am+1 + am+2 + · · · + an−1 + an .
i =m

Let {an } be an arithmetic sequence. Then the sum of its first n terms is

n
X
Sn = ai = (a1 + an ) × n ÷ 2.
i =1

More generally, if m < n, the sum from the m th term to the n th term (both inclusive) is

[(initial term) + (last term)] × (numer of terms) ÷ 2 = (am + an ) × (n − m + 1) ÷ 2 .

Example 1.2.4. Find the sum of the first 1000 terms of the arithmetic sequence

12, 15, 18, 21, . . ..

CHAPTER 1. SEQUENCES 9

Solution. The 1st term a = 12 and the common difference d = 3. Then the 1000th term is

a1000 = a + 999d = 12 + 999 × 3 = 3009.

So the sum of the first 1000 terms is

(12 + 3009) × 1000 ÷ 2 = 1510500.

Example 1.2.5. Find the sum of the arithmetic sequence

123 + 154 + 185 + · · · + 7253 + 7284.

Solution. The 1st term a = 123 and common difference d = 154 − 123 = 31. Suppose that there
are n terms in the sum. Then the n th term of the sequence is an = 7284, which implies

7284 = a + (n − 1)d = 92 + 31n ⇒ n = 232.

Therefore, the sum of the arithmetic sequence is

(123 + 7284) × 232 ÷ 2 = 859212.

Example 1.2.6. Find the smallest positive integer n so that the sum of the first n terms of the
following arithmetic sequence exceeds 5000:

6, 13, 20, 27, 34, . . . .

Solution. The 1st term a = 6 and common difference d = 7. The n th term of the arithmetic
sequence is an = a + (n − 1)d = 6 + (n − 1)7 = 7n − 1. So the sum of the first n terms is

S n = [6 + (7n − 1)] × n ÷ 2 = (7n 2 + 5n) ÷ 2.

Then
S n > 5000 ⇔ (7n 2 + 5n) ÷ 2 > 5000 ⇔ 7n 2 + 5n − 10000 > 0.

Since the two real solutions of 7x 2 + 5x − 10000 = 0 are x1 ≈ −38.2 and x2 ≈ 37.4, we have

S n > 5000 ⇔ n < −38.2 or n > 37.4 ⇔ n ≥ 38 (n is a positive integer).

Therefore, the smallest n so that S n > 5000 is n = 38.

CHAPTER 1. SEQUENCES 10

1.2.3 Geometric Sequences

Definition of geometric sequence

A sequence {an } is called a geometric sequence of common ratio r if its 1st term a 6= 0 and the
ratio of any two consecutive terms is r :

an+1 = an r, n = 1, 2, 3, . . ..

Let a 6= 0 be the 1st term and r be the common ratio of a geometric sequence {an }. Then

an = ar n−1 .

More generally,
an = am r n−m .

Example 1.2.7. A geometric sequence is given such that (i) the 1st term exceeds the 3rd term by
112, and (ii) the 2nd term exceeds the 4th term by 84.

(i) Find the 1st term and the common ratio of the geometric sequence.
(ii) Find the number of terms of the geometric sequence which exceed 50.

Solution. (i) Let a be the 1st term and r be the common ratio of the geometric sequence. Then
the n th term is an = ar n−1 . By assumption,

112 = a1 − a3 = a − ar 2 and 84 = a2 − a4 = ar − ar 3 .

Then 84 = ar − ar 3 = (a − ar 2 )r = 112r implies r = 84/112 = 3/4. So

112 = a − ar 2 = a(1 − r 2 ) = a(1 − 9/16) = 7a/16 ⇒ a = 256.

µ ¶n−1
n−1 3
(ii) an = ar = 256 . Then
4
µ ¶n−1 µ ¶n−1
3 25 4 128 128 ln(128/25)
an > 50 ⇔ > ⇔ < ⇔ n − 1 < log 4 = ≈ 5.7 ⇔ n < 6.7.
4 128 3 25 3 25 ln(4/3)
Note that n is a positive integer. Then 1 ≤ n ≤ 6. The sequence has 6 terms which exceed 50.

Sum of geometric sequences

Let {an } be a geometric sequence for which the 1st term is a (6= 0) and the common ratio is r .
Then the sum of its first n terms is given by
( a
n
X (1 − r n ) if r =
6 1,
Sn = ai = 1−r
i =1 na if r = 1.
CHAPTER 1. SEQUENCES 11

Example 1.2.8. Consider a segment of length 1. Cut half in the 1st day, and cut half of the
remaining for each of the following days. How much have we cut by the 100th day?
1
32
1
16
1 1 1
2 4 8

Solution. Let an be the length of the segment cut in the n th day. Then {an } is a geometric se-
quence whose 1st term a = 1/2 and the common ratio r = 1/2. By the 100th day, we have cut
100 · µ ¶100 ¸
X a 100 1/2 1 1
S 100 = an = (1 − r ) = 1− = 1 − 100 .
i =1 1−r 1 − 1/2 2 2

Example 1.2.9. Put 1 grain of rice in the 1st square of an 8 ×8 chessboard, and double the num-
ber in the next square. How much rice do we need to fill in the chessboard?

Solution. Let an be the number of grains of rice in the n th square. Then {an } is a geometric
sequence with 1st term a = 1 and common ratio r = 2. In order to fill in the chessboard, we need
64 1
(1 − 264 ) = 264 − 1 = 18446744073709551615.
X
S 64 = ai =
i =1 1−2
Note that this is more than 1000 years of the world rice production!
Example 1.2.10. Find the smallest positive integer n so that the sum of the first n terms of the
following geometric sequence exceeds 30:

5/6, 1, 6/5, . . . .

Solution. The 1st term of the sequence a = 5/6 and the common ratio r = 1 ÷ (5/6) = 6/5.
· µ ¶n ¸
25 6 n
·µ ¶ ¸
a n 5/6 6
Sn = (1 − r ) = 1− = −1 .
1−r 1 − 6/5 5 6 5
Then µ ¶n
6 25 41 41 ln(41/5)
S n > 30 ⇔ > 30 ÷ +1 = ⇔ n > log 6 = ≈ 11.5.
5 6 5 5 5 ln(6/5)
Note that n is a positive integer. So the smallest positive integer n so that S n > 30 is 12.
CHAPTER 1. SEQUENCES 12

1.2.4 Limit of Sequences

Definition of limit

Let {an } be a sequence. If as n gets large, an approaches a fixed number L (n → ∞ ⇒ an → L),

then {an } is convergent to the limit L, denoted by lim an = L. If {an } is not convergent, then
n→∞
{an } is divergent.
If as n gets large, an gets arbitrarily large (n → ∞ ⇒ an → ∞), we write lim an = ∞. If as
n→∞
n gets large, an gets arbitrarily negatively large (n → ∞ ⇒ an → −∞), we write lim an = −∞.
n→∞
Note that if lim an = ∞ or −∞, the limit makes sense but does not exist.
n→∞

Example 1.2.11. Let an = n/(n +1). We can see from the following figure that as n gets large, an
approaches 1, i.e., lim n/(n + 1) = 1.
n→∞

y
1 b b b b b b b b b b b b
b b
b
b
b
b

x
O 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Alternatively, we can compute the limit directly. Note that lim 1/n = 0. Then
−1 n→∞

n n/n 1 1
lim = lim = lim = = 1.
n→∞ n + 1 n→∞ (n + 1)/n n→∞ 1 + 1/n 1+0

Example 1.2.12. Let b n = cos(nπ/6). As n gets large, b n does not approach any fixed number.
y
1 b b
b
b

b b b

b b b
x
O 1 2 3 4
b
5 6 7 8
b
9 10 11 12 13 14 15 16
b
17 18 19

b b b b

−1 b b

So lim cos(nπ/6) is divergent.

n→∞

Properties 1.2.13 (Limits of Sequences). Let {an } and {b n } be convergent sequences. Then

(i) lim can = c lim an (c ∈ R). (ii) lim (an ± b n ) = lim an ± lim b n .
n→∞ n→∞ n→∞ n→∞ n→∞
(iii) lim (an b n ) = lim an · lim b n . (iv) lim (an /b n ) = lim an / lim b n , if lim b n 6= 0.
n→∞ n→∞ n→∞ n→∞ n→∞ n→∞ n→∞
(v) If an ≤ b n for all n, then lim an ≤ lim b n .
n→∞ n→∞
CHAPTER 1. SEQUENCES 13

Theorem 1.2.14 (Squeeze Theorem for Limits). Let {an }, {b n } and {cn } be sequences such that
an ≤ b n ≤ cn for all n. If {an } and {cn } are both convergent with lim an = lim cn = L, then {b n }
n→∞ n→∞
is also convergent with lim b n = L.
n→∞

Example 1.2.15. Prove that 0 < n!/n n ≤ 1/n for all positive integer n. Hence, evaluate lim n!/n n .
n→∞

n! 1 × 2 × · · · × (n − 1) × n 1 2 n −1 n 1 1
Solution. 0 < n
= = × ×··· × × ≤ ×1 ×··· ×1 ×1 = .
n n ×n ×··· ×n ×n n n n n n n
Since lim 0 = 0 and lim 1/n = 0, by squeeze theorem, lim n!/n n = 0.
n→∞ n→∞ n→∞

Sum to infinity of geometric sequences

Let {an } be a sequence, and S n = a1 + · · · + an be the sum of its first n terms. Then
∞
X
S ∞ = lim S n = a1 + a2 + · · · + an + · · · = an
n→∞
n=1

is the (infinite) series associated to {an }.

Let {an } be the geometric sequence whose 1st term is a 6= 0 and the common ratio is r . Then

∞
( a
X n−1 if − 1 < r < 1,
S∞ = ar = 1−r
n=1 does not exist if r ≤ −1 or r ≥ 1.

Example 1.2.16. Evaluate each of the following geometric series if it exists.

(a) 1 + 1/3 + 1/32 + 1/33 + · · · ; (b) 1 − 1/2 + 1/22 − 1/23 + · · · ;

(c) 1 + x + x 2 + x 3 + · · · where −1 < x < 1; (d) 1 + 2 + 4 + 8 + 16 + · · · .

Answer: (a) 3/2; (b) 2/3; (c) 1/(1 − x); (d) does not exist.

Example 1.2.17. Express the recurring decimal 1.123232323 · · · as a rational number.

Solution. Note that

0.023232323 · · · = 0.023 + 0.00023 + 0.0000023 + 0.000000023 + · · ·

is the geometric series whose 1st term a = 0.023 and common ratio r = 0.01. Then

1.123232323 · · · = 1.1 + (0.023 + 0.00023 + 0.0000023 + 0.000000023 + · · ·)

0.023 11 23 556
= 1.1 + = + = .
1 − 0.01 10 990 495
CHAPTER 1. SEQUENCES 14

1.2.5 Telescoping Sum

A telescoping sum is a sum of sequence which has a fixed number of terms after cancelation.
Consider a sequence {an }, and define a new sequence u n = an − an+1 . Then for m ≤ n,
n
X
u i = u m + u m+1 + · · · + u n = (am − am+1 ) + (am+1 − am+2 ) + · · · + (an − an+1 ) = am − an+1 .
i =m

100
X 1 1 1 1 1
Example 1.2.18. Find S = = + + +··· + .
n=1 n(n + 1) 1×2 2×3 3×4 100 × 101

1 A B (A + B)n + A
Solution. Let = + = . Compare coefficients of numerators to get
n(n + 1) n n + 1 n(n + 1)

A + B = 0 and A = 1.

Then A = 1 and B = −1, and 1/n(n + 1) = 1/n − 1/(n + 1). Therefore,

µ ¶ µ ¶ µ ¶ µ ¶
1 1 1 1 1 1 1 1 1 1 100
S= − + − + − +··· + − = − = .
1 2 2 3 3 4 100 101 1 101 101

cot nθ − cot(n + 1)θ 1

Example 1.2.19. (i) Prove that = .
sin θ sin nθ sin(n + 1)θ
XN 1
(ii) Using the identity in (i), evaluate .
n=1 sin nθ sin(n + 1)θ

Solution. (i) Note that cot α = cos α/ sin α. Then by Properties 1.1.6(iv),
µ ¶
cot nθ − cot(n + 1)θ 1 cos nθ cos(n + 1)θ
= −
sin θ sin θ sin nθ sin(n + 1)θ
1 sin(n + 1)θ cos nθ − cos(n + 1)θ sinnθ
= ·
sin θ sin nθ sin(n + 1)θ
1 sin[(n + 1)θ − nθ] 1
= · = .
sin θ sin nθ sin(n + 1)θ sin nθ sin(n + 1)θ

(ii) Using the result in (i),

N
X 1 XN cot nθ − cot(n + 1)θ 1 X N
= = [cot nθ − cot(n + 1)θ]
n=1 sin nθ sin(n + 1)θ n=1 sin θ sin θ n=1
1
= [(cot θ − cot 2θ) + (cot 2θ − cot 3θ) + · · · + (cot N θ − cot(N + 1)θ)]
sin θ
1
= [cot θ − cot(N + 1)θ] .
sin θ
CHAPTER 1. SEQUENCES 15

1.3 Binomial Theorem

1.3.1 Binomial Theorem

Binomial coefficients

Let n be a nonnegative integer and r an integer such that 0 ≤ r ≤ n. The binomial coefficient is
à !
n n! n(n − 1)(n − 2) · · ·[n − (r − 1)]
= = , where n! = 1 × 2 × · · · × n.
r r ! (n − r )! r!

It represents the number of ways to form a group of r people from n people, read as n choose r .
à ! à !
n n n!
Remark. For convention, 0! = 1. So = = = 1.
0 n 0! × n!
The Pascal’s triangle is constructed so that each number is the sum of the two numbers
directly above it.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
à ! à ! à !
0 1 1
The top row is the 0th row, which represents , the 1st row represents and . In general,
0 0 1
the n th row represents the binomial coefficients
à ! à ! à ! à ! à !
n n n n n
, , , ..., , .
0 1 2 n −1 n

For example,
à ! à ! à ! à ! à ! à ! à !
6 6 6 6 6 6 6
= 1, = 6, = 15, = 20, = 15, = 6, = 1.
0 1 2 3 4 5 6

Binomial Theorem

Theorem 1.3.1 (Binomial Theorem). Let n be a nonnegative integer. Then

à ! à ! à ! à ! à ! à !
n n n n n n−1 n n−2 2 n n n
n n−r r n−1
X
(a + b) = a b = a + a b+ a b +··· + ab + b .
r =0 r 0 1 2 n −1 n
CHAPTER 1. SEQUENCES 16

For example,
(a + b)6 = a 6 + 6a 5 b + 15a 4 b 2 + 20a 3 b 3 + 15a 2 b 4 + 6ab 5 + b 6 .

Example 1.3.2. Expand (3 + 2x)5 .

Solution. By binomial theorem,

(a + b)5 = a 5 + 5a 4 b + 10a 3 b 2 + 10a 2 b 3 + 5ab 4 + b 5 .
Let a = 3 and b = 2x. Then
(3 + 2x)5 = (3)5 + 5(3)4 (2x) + 10(3)3 (2x)2 + 10(3)2 (2x)3 + 5(3)(2x)4 + (2x)5
= 243 + 810x + 1080x 2 + 720x 3 + 240x 4 + 32x 5 .

Example 1.3.3. Find the coefficient of x 3 in the expansion of (3 + 2x)6 .

Solution. Method 1: Using the result in the previous example,

(3 + 2x)6 = (3 + 2x)5 (3 + 2x) = (· · · + 1080x 2 + 720x 3 + · · · )(3 + 2x)
= · · · + (1080x 2 )(2x) + (720x 3 )(3) + · · ·
= · · · + 4320x 3 + · · · .
Method 2: By binomial theorem, (3 + 2x)6 is the sum of
à ! à !
6 6−r 6 6−r r r
3 (2x)r = 3 2 · x , r = 0, 1, 2, . . ., 6.
r r
à !
6 6−r r
So the coefficient of x r in the expansion of (3 + 2x)6 is 3 2 . In particular, let r = 3; then
r
à !
3 6 6−3 3
the coefficient of x is 3 2 = 4320.
3

2 12
µ ¶
2
Example 1.3.4. In the expansion of 3x − , find (i) the coefficient of x −9 , and (ii) the con-
x
stant term.
2 12
µ ¶
2
Solution. 3x − is the sum of
x
à ! à ! µ ¶r à !
2 r
µ ¶
12 2 12−r 12 12−r r 2(12−r ) 1 12 12−r
(3x ) − = 3 (−2) ·x = 3 (−2)r ·x 24−3r , r = 0, 1, 2, . . ., 12.
r x r x r
à !
12 12−11
(i) Let 24 − 3r = −9. Then r = 11. So the coefficient of x is −9
3 (−2)11 = −73728.
11
0
(ii) Note that the
à !constant term is the coefficient of x . Let 24 − 3r = 0. Then r = 8. So the
12 12−8
constant term is 3 (−2)8 = 10264320.
8
CHAPTER 1. SEQUENCES 17

1.3.2 Generalized Binomial Theorem

Generalized binomial coefficients

Let r be a nonnegative integer. For any number n, the generalized binomial coefficient is
à !
n n(n − 1)(n − 2) · · ·[n − (r − 1)]
= .
r r!

For example, Ã !
1/2 (1/2)(−1/2)(−3/2) 1
= = .
3 3! 16
Remark. If n is a nonnegative integer and 0 ≤ r ≤ n, then the definition of generalized binomial
coefficient agrees with the definition of binomial coefficient in Section 1.3.1.

Generalized binomial theorem

Theorem 1.3.5 (Generalized Binomial Theorem). For any number n, if −1 < a < 1, then
à ! à ! à ! à !
n n n n r
(1 + a)n = + a+ a2 + · · · + a +··· .
0 1 2 r
à !
n
Remark. (i) By convention, = 1 for all number n.
0
à !
n
(ii) If n is a nonnegative integer, then = 0 for all integers r > n, and the generalized
r
binomial theorem reduces to a special case of the binomial theorem (Theorem 1.3.1, b = 1):
à ! à ! à ! à ! à !
n n n n 2 n n−1 n n
(1 + a) = + a+ a +··· + a + a .
0 1 2 n −1 n

In application, Theorem 1.3.5 is used only when n is not a nonnegative integer.

Example 1.3.6. Expand 1/(1 − x) up to and including the term in x 4 , and find the range of x
when the expansion is valid.

Solution. 1/(1 − x) = [1 + (−x)]−1 . Let n = −1 and a = −x. Then

à ! à ! à ! à ! à !
1 −1 −1 −1 −1 −1
= + (−x) + (−x)2 + (−x)3 + (−x)4 + · · ·
1−x 0 1 2 3 4
−1 (−1)(−2) 2 (−1)(−2)(−3) 3 (−1)(−2)(−3)(−4) 4
= 1− x+ x − x + x +···
1! 2! 3! 4!
= 1 + x + x2 + x3 + x4 + · · · .

The expansion is valid ⇔ −1 < −x < 1 ⇔ −1 < x < 1.

CHAPTER 1. SEQUENCES 18

p
Example 1.3.7. Expand 1/ 4 + 3x up to and including the term in x 2 , and find the range of x
p p
when the expansion is valid. Moreover, use x = 1/3 and x = 1/4 to approximate 5 and 19
respectively using rational numbers.
¶−1/2
3x −1/2
µ µ ¶
1 −1/2 −1/2 3x 1
Solution. p = (4 + 3x) =4 1+ = 1+ . Let a = 3x/4, n = −1/2.
4 + 3x 4 2 4

3x −1/2 (−1/2)(−1/2 − 1) 3x 2
µ ¶ µ ¶ µ ¶
−1/2 3x 3 27 2
1+ = 1+ + +··· = 1 − x + x +··· .
4 1 4 2! 4 8 128
Hence, µ ¶
1 1 3 27 2 1 3 27 2
p = 1− x + x +··· = − x + x +··· .
4 + 3x 2 8 128 2 16 256
The expansion is valid ⇔ −1 < 3x/4 < 1 ⇔ −4/3 < x < 4/3.
Let x = 1/3. Then
1 1 1 3 115
LHS = p and RHS ≈ − + = .
5 2 16 256 256
p
Hence, 5 ≈ 256/115.
Let x = 1/4. Then
1 2 1 3 27 1883
LHS = p =p and RHS ≈ − + = .
4 + 3/4 19 2 64 4096 4096
p p
Hence, 19/2 ≈ 4096/1883; or equivalently, 19 ≈ 8192/1883.

1.4 Mathematical Induction

The mathematical induction is a technique to prove statements on successive integers.
Let P (n) be a statement on integers n = n 0 , n 0 + 1, n 0 + 2, . . . .

(i) Initial step: Verify that P (n 0 ) is true.

(ii) Inductive step: Verify that P (k) ⇒ P (k + 1) is true for any integer k ≥ n 0 , i.e., assume that
P (k) is true for some k ≥ n 0 , and then use this fact to verify that P (k + 1) is also true.

Then mathematical induction concludes that P (n) is true for every integer n ≥ n 0 .

Example 1.4.1. Prove that S n = 1 + 3 + 5 + · · · + (2n − 1) = n 2 for all positive integer n.

Proof. Let P (n) be the statement that S n = n 2 .

(i) Initial step: P (1) is the statement that S 1 = 12 .

LHS = S 1 = 1 and RHS = 12 = 1.

Hence, P (1) is true.

CHAPTER 1. SEQUENCES 19

(ii) Inductive step: Assume that P (k) is true for some integer k ≥ 1, i.e., S k = k 2 . We need to use
this to prove that P (k + 1) is true, i.e., S k+1 = (k + 1)2 .

S k+1 = 1 + 3 + · · · + (2k − 1) + [2(k + 1) − 1] = S k + (2k + 1) = k 2 + (2k + 1) = (k + 1)2 .

Hence, P (k + 1) is also true.

By mathematical induction, P (n) is true for every positive integer n; that is, S n = n 2 .

Example 1.4.2. Prove that 2n < 2n for all integers n > 2.

Proof. Let P (n) be the statement that 2n < 2n .

(i) Initial step: P (3) is the statement that 2 × 3 < 23 .

LHS = 2 × 3 = 6 < RHS = 23 = 8.

Hence, P (3) is true.

(ii) Inductive step: Assume that P (k) is true for some integer k > 2, i.e., 2k < 2k . We need to
use this to prove that P (k + 1) is true, i.e., 2(k + 1) < 2k+1 .

2(k + 1) = 2k + 2 < 2k + 2 < 2k + 2k = 2 × 2k = 2k+1 .

Hence, P (k + 1) is also true.

By mathematical induction, P (n) is true for every integer n > 2; that is, 2n < 2n .

Example 1.4.3. Prove that 24n+3 + 33n+1 is divisible by 11 for any positive integer n.

Proof. Let P (n) be the statement that 24n+3 + 33n+1 is divisible by 11.

(i) Initial step: P (1) is the statement 24×1+3 + 33×1+1 is divisible by 11.

24×1+3 + 33×1+1 = 27 + 34 = 209 = 11 × 19.

So P (1) is true.
(ii) Inductive step: Assume that P (k) is true for some integer k ≥ 1, i.e., 24k+3 +33k+1 is divisible
by 11; so it is of the form 11N some integer N . We need to use this to prove that P (k + 1) is
true, i.e., 24(k+1)+3 + 33(k+1)+1 is also divisible by 11.

24(k+1)+3 + 33(k+1)+1 = 24k+3+4 + 33k+1+3 = 16 × 24k+3 + 27 × 33k+1

= 16 × (24k+3 + 33k+1 ) + 11 × 33k+1 = 16 × 11N + 11 × 33k+1 = 11 × (16N + 33k+1 ).

This is divisible by 11. So P (k + 1) is also true.

By mathematical induction, P (n) is true for every positive integer n; that is, 24n+3 + 33n+1 is
divisible by 11.
CHAPTER 1. SEQUENCES 20

1.5 Exercises
Sequences

1.1. It is given that the 3rd and 7th terms of an arithmetic sequence are 175 and 105 respectively.

(i) Find the 1st term and common difference of the sequence.
(ii) Find the positive integer n so that the sum of the first n terms of the sequence is zero.

1.2. The sum of 3 consecutive terms of a geometric sequence is 28 and their product is 512.
Find these numbers.

1.3. The sum of the first 4 terms of a geometric sequence is 3.75, and the sum to infinity is 4.
Find the 1st term and common ratio of the sequence.

1.4. The common difference of an arithmetic sequence is 1, and the common ratio of a geomet-
ric sequence is 3. A new sequence is formed by adding the corresponding terms of these two
sequences. Suppose that the 2nd and 4th terms of the new sequence are 12 and 86 respectively.

(i) Find the n th term of the new sequence.

(ii) Find the sum of the first n terms of the new sequence.

1.5. Find the value of x for which

3x + 6, x + 2, 34 − x

are successive terms of a geometric sequence.

1.6. An arithmetic sequence with 1st term a and common difference d (6= 0) is given such that
its 3rd , 6th and 10th terms are successive terms of a geometric sequence.

(i) Show that a = 7d .

(ii) Find the ratio of the sum of the first 30 terms to the sum of the first 10 terms of the arith-
metic sequence.

1.7. Express the recurring decimal 0.345 345 345 · · · as a rational number.

1.8. The first two terms of a geometric sequence are x + 2 and x 2 − 2x − 8 respectively.

(i) Find the range of x for which the sum of the sequence to infinity exists.
(ii) Find the sum of the sequence to infinity, in terms of x, when it exists.

1.9. Express the following sums in Sigma notation and evaluate them.

(a) ln 2 + ln 4 + ln8 + ln 16 + · · · + ln 2048.

(b) 3 + 5 + 25/3 + 125/9 + 625/27 + · · ·, up to 2n terms.
CHAPTER 1. SEQUENCES 21

1.10. (a) Find the smallest positive integer n for which the sum of the first n terms of the fol-
lowing arithmetic sequence exceeds 1500:

5, 8, 11, 14, . . . .

(b) Find the smallest positive integer n for which the sum of the first n terms of the following
geometric sequence exceeds 127.95:

64, 32, 16, . . . .

1.11. Evaluate the following telescoping sums:

X99 µ
r +1
¶
XN 1
(a) lg , (b) 2
.
r =1 r r =2 4r − 1
1.12. (i) Show that for any positive integer r ,

(r + 1)! − r ! = r (r !).

(ii) Using the result in (i) show that

m
X
r (r !) = (m + 1)! − 1.
r =1

Binomial theorem

1.13. (i) Expand (2 − 3x)6 in ascending powers of x.

(ii) Find the coefficient of x 3 in the expansion of (2 − 3x)8 .
(iii) Find the value a for which the coefficient of x in the expansion of (1 + ax)(2 − 3x)6 is zero.
1.14. For each of the following, find the constant term of the expansion:
1 12 4 9
µ ¶ µ ¶
x
(a) 3x − , (b) +p .
x 2 x
1.15. Use the binomial theorem to show that for all nonnegative integer n,
à ! à ! à ! à ! à !
n n n n n
+ + +··· + + = 2n .
0 1 2 n −1 n
p
1.16. (i) Expand 1 − x up to and including the term in x 2 .
p
(ii) By taking x = 1/64 in the expansion in (i), deduce that 7 ≈ 10837/4096.
1.17. (i) Express x/(x 2 − 3x + 2) in the form A/(x − 1) + B/(x − 2), where A, B are constants.
(ii) Show that for sufficiently small x,
x 1 3
≈ x + x2.
x 2 − 3x + 2 2 4
1.18. Show that for sufficiently small x,
r
4−x 5 55
≈ 2 − x + x2.
1+x 4 64
CHAPTER 1. SEQUENCES 22

Mathematical induction

1.19. Prove the following identities by mathematical induction:

n 1 n 3 n −1
r 2 = n(n + 1)(2n + 1);
X X
(a) (b) = .
r =1 6 r =2 (r + 1)(r + 2) n +2

1.20. The sequence {u n } is defined by

³ un ´
u 1 = 2 and u n+1 = 2 u n + for n ≥ 1.
n
(i) Evaluate the values of u 2 , u 3 and u 4 .
(ii) Prove by mathematical induction that u n = n · 2n for every positive integer n.

Hints to Exercises

1.1. (i) 1st term 210; common difference −35/2. (ii) 25.

1.2. 4, 8, 16 (or 16, 8, 4). Hint: Let a be the 1st term and r the common ratio. Then the three
numbers are a, ar and ar 2 .

1.3. Two sets of solutions: 1st term 2 and common ratio 1/2, 1st term 6 and common ratio
−1/2.

1.4. (i) n + 1 + 3n . (ii) n(n + 3)/2 + 3(3n − 1)/2. Hint: The sum of the first n terms of the new
sequence equals the sum of that of the arithmetic sequence and that of the geometric sequence.

1.5. x = 25. Hint: If r is the common ratio, then r = (x + 2)/(3x + 6) = (34 − x)/(x + 2).

1.6. (i) Hint: If a, b, c are the successive terms of a geometric sequence, then the common ratio
is given by r = a/b = c/b. (ii) 129/23.

1.7. 115/333. Hint: It is the geometric series with 1st term 0.345 and common ratio 0.001.

1.8. (i) 3 < x < 5. (ii) (x + 2)/(5 − x).

1.9. (a) 66 ln2. Hint: ln(a r ) = r ln a. (b) (9/2)[(5/3)2n − 1].

1.10. (a) 31. (b) 12.

1.11. (a) 2. Hint: lg(a/b) = lg a − lg b. (b) 1/6 − 1/[2(2N + 1)]. Hint: Express 1/(4r 2 − 1) as
A/(2r − 1) + B/(2r + 1) for some constants A, B.

1.12. (i) Hint: (r + 1)! = 1 × 2 × · · · × r × (r + 1) = r !(r + 1). (ii) Hint: Telescoping sum.

1.13. (i) 64 − 576x + 2160x 2 − 4320x 3 + 4860x 4 − 2916x 5 + 729x 6 . (ii) −48384. 9.

1.14. (a) 673596. (b) 43008. Hint: The constant term is the coefficient of x 0 .
CHAPTER 1. SEQUENCES 23

1.15. Hint: Let a = b = 1 in the binomial theorem.

p
1.16. (i) 1 − x/2 − x 2 /8 + · · · . Hint: 1 − x = [1 + (−x)]1/2 .

1.17. (i) −1/(x −1)+2/(x −2). (ii) Hint: −1/(x −1) = [1+(−x)]−1 and 2/(x −2) = − [1 + (−x/2)]−1 .
p p
1.18. Hint: Find the approximations of 4 − x = 2 [1 + (−x/4)]1/2 and 1/ 1 + x = (1 + x)−1/2 up
p p p
to the term in x 2 . Then note that (4 + x)/(1 + x) = 4 − x × 1/ 1 + x.
k+1 k
r2 = r 2 + (k + 1)2 .
X X
1.19. (a) Hint:
r =1 r =1
k+1
X 3 X k 3 3
(b) Hint: = + .
r =2 (r + 1)(r + 2) r =2 (r + 1)(r + 2) [(k + 1) + 1][(k + 1) + 2]

1.20. (i) 8, 24, 64.