Combinatorics • Topic 13

Sequences

A sequence is an ordered list of numbers. In Olympiads, we analyze their patterns, growth, and limits.

Types of Sequences

Each term is the previous term plus a constant difference

d

a_{n} = a_{1} + (n - 1) d

Sum of first $n$ terms:

S_{n} = \frac{n}{2} (a_{1} + a_{n})

Each term is the previous term multiplied by a constant ratio

r

a_{n} = a_{1} \cdot r^{n - 1}

Sum of first $n$ terms:

S_{n} = a_{1} \frac{r ^{n} - 1}{r - 1} (r \neq = 1)

Infinite Sum ( $∣ r ∣ < 1$ ):

S_{\infty} = \frac{a _{1}}{1 - r}

Defined by a relation between terms, e.g., Fibonacci:

F_{n} = F_{n - 1} + F_{n - 2}

Olympiad problems often ask to prove a sequence is bounded or monotonic.

Exercise (Problem 1)

The sum of the first

n

terms of an arithmetic sequence is

S_{n} = 2 n^{2} + 3 n

. Find the

n

-th term

a_{n}

Exercise (Problem 2)

Evaluate the infinite sum:

\frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \frac{4}{16} + \dots

(Arithmetico-Geometric Series).

Exercise (Problem 3)

Let

a_{1} = 1

and

a_{n + 1} = \frac{1}{1 + a _{n}}

. Find the limit of

a_{n}

n \to \infty