Sums and patterns

This chapter delves into the fundamental concepts of sums and patterns, essential for a robust understanding of Algebra and Functions. It equips students with techniques for analyzing sequences, deriving sum formulas, and applying advanced summation methods crucial for problem-solving and subsequent mathematical studies. Mastery of these topics is critical for success in the CMI examinations.

---

Chapter Contents

| Topic |

|---|-------| | 1 | Pattern recognition in sequences | | 2 | Recursively defined sequences | | 3 | Sum formulas | | 4 | Telescoping sums |

---

We begin with Pattern recognition in sequences.

Part 1: Pattern recognition in sequences

Pattern recognition in sequences

Overview

Pattern recognition in sequences is the first real skill in sequence problems. A formula is often not given directly; instead, you must detect structure from the terms. In CMI-style questions, the sequence may hide an arithmetic pattern, a geometric pattern, a polynomial pattern, an alternating sign, or a recursive rule. The goal is to identify the mechanism generating the sequence. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Recognise arithmetic, geometric, alternating, and recursive patterns.

Use first differences, second differences, and ratios effectively.

Detect hidden polynomial behaviour in sequences.

Predict the next term or derive the $n$ th term from a pattern.

Avoid overfitting a pattern from too few terms.

---

Core Idea

📖 What is a sequence pattern?

A sequence is an ordered list of numbers:
$\qquad a_1,\ a_2,\ a_3,\ \dots$

Pattern recognition means identifying the rule that connects:

one term to the next, or

the term number $n$ to the term $a_n$ , or

blocks of terms to a known algebraic structure.

❗ Main Types of Patterns

The most common patterns are:

constant difference

constant ratio

alternating sign

polynomial growth

recursive dependence

telescoping-type cancellation in related sums

---

Arithmetic Pattern

📐 Arithmetic sequence

If consecutive terms differ by a constant $d$ , then the sequence is arithmetic:

$\qquad a_{n+1}-a_n=d$

Then
$\qquad a_n=a_1+(n-1)d$

Examples:

$3,7,11,15,\dots$ has difference $4$

$10,6,2,-2,\dots$ has difference $-4$

---

Geometric Pattern

📐 Geometric sequence

If consecutive terms have a constant ratio $r$ , then the sequence is geometric:

$\qquad \dfrac{a_{n+1}}{a_n}=r$

Then
$\qquad a_n=a_1r^{n-1}$

Examples:

$2,6,18,54,\dots$ has ratio $3$

$81,27,9,3,\dots$ has ratio $\dfrac{1}{3}$

:::

⚠️ Do Not Confuse Difference and Ratio

arithmetic pattern $\to$ constant difference

geometric pattern $\to$ constant ratio

A sequence can have neither.

---

Difference Method

📐 First and second differences

For a sequence $a_1,a_2,a_3,\dots$ :

first differences:

\qquad \Delta a_n=a_{n+1}-a_n

second differences:

\qquad \Delta^2 a_n=\Delta a_{n+1}-\Delta a_n

If first differences are constant, the sequence is linear in

n

.

If second differences are constant, the sequence is quadratic in

n

Examples:

$2,5,8,11,\dots$

first differences:

3,3,3,\dots

$1,4,9,16,\dots$

first differences:

3,5,7,\dots

second differences:

2,2,\dots

So squares show a quadratic pattern. ---

Polynomial Pattern Clues

📐 Useful standard patterns

$1,2,3,4,\dots \to a_n=n$

$1,4,9,16,\dots \to a_n=n^2$

$1,8,27,64,\dots \to a_n=n^3$

$2,5,10,17,\dots \to a_n=n^2+1$

$1,3,6,10,\dots \to a_n=\dfrac{n(n+1)}{2}$

💡 Triangular Number Pattern

The sequence
$\qquad 1,3,6,10,15,\dots$
has first differences
$\qquad 2,3,4,5,\dots$

So it is built by repeated addition of consecutive integers:

$\qquad a_n=\dfrac{n(n+1)}{2}$

---

Alternating Pattern

📐 Alternating sign

If signs alternate, common factors include:

$(-1)^n$

$(-1)^{n-1}$

Examples:

$1,-1,1,-1,\dots = (-1)^{n-1}$

$2,-4,8,-16,\dots = 2^n(-1)^{n-1}$

❗ Check the starting index

When using $(-1)^n$ or $(-1)^{n-1}$ , always check whether the first term should be positive or negative.

---

Recursive Pattern

📖 Recursive rule

A sequence is recursive if each term is defined using previous terms.

Examples:

$a_{n+1}=a_n+3$

$a_{n+1}=2a_n+1$

$a_{n+2}=a_{n+1}+a_n$

Recursive patterns are common in olympiad and entrance problems.

💡 How to inspect a recursive pattern

Look for:

constant added each step

constant multiplied each step

a combination of both

dependence on the previous two terms

---

Minimal Worked Examples

Example 1 Identify the pattern:

\qquad 3,8,15,24,35,\dots

First differences are

\qquad 5,7,9,11,\dots

Second differences are constant:

\qquad 2,2,2,\dots

So the sequence is quadratic in

n

. Try

\qquad a_n=n^2+2n

Check:

$n=1 \Rightarrow 3$

$n=2 \Rightarrow 8$

$n=3 \Rightarrow 15$

\qquad a_n=n^2+2n

--- Example 2 Identify the pattern:

\qquad 2,-6,18,-54,\dots

The ratio is

\qquad -3

So the sequence is geometric:

\qquad a_n=2(-3)^{n-1}

---

Pattern Building Strategy

💡 CMI Strategy

When a sequence is given, inspect in this order:

Is the difference constant?

Is the ratio constant?

Are the signs alternating?

Are first or second differences structured?

Does the sequence resemble squares, cubes, or triangular numbers?

Could the rule depend recursively on previous terms?

---

Standard Reference Patterns

📐 Patterns worth memorising

natural numbers:

\qquad n

odd numbers:

\qquad 2n-1

even numbers:

\qquad 2n

squares:

\qquad n^2

cubes:

\qquad n^3

triangular numbers:

\qquad \dfrac{n(n+1)}{2}

powers of $2$ :

\qquad 2^{n-1}

alternating powers:

\qquad (-2)^{n-1}

2^{n-1}(-1)^{n-1}

---

Common Errors

⚠️ Avoid These Errors

❌ deciding a formula from only two or three terms without testing

❌ confusing arithmetic and geometric patterns

❌ ignoring alternating sign

❌ forgetting that quadratic patterns have constant second differences, not first differences

❌ writing $(-1)^n$ when $(-1)^{n-1}$ is needed

❌ assuming every pattern has a unique continuation without extra conditions

✅ Correct habits:

test your formula on all known terms

check differences and ratios

look for known number patterns

verify the starting index carefully

---

Practice Questions

:::question type="MCQ" question="The sequence

4, 9, 16, 25, \dots

is best described by which formula?" options=["

a_n=n^2

","

a_n=(n+1)^2

","

a_n=2n+2

","

a_n=n^2+1

"] answer="B" hint="Compare the first few squares." solution="We have

\qquad 4=2^2,\ 9=3^2,\ 16=4^2,\ 25=5^2

So the

n

th term is

\qquad a_n=(n+1)^2

Hence the correct option is

\boxed{B}

." ::: :::question type="NAT" question="If the sequence is

2,5,10,17,26,\dots

, find the next term." answer="37" hint="Look at first differences." solution="The first differences are

\qquad 3,5,7,9

These are consecutive odd numbers, so the next difference is

\qquad 11

Hence the next term is

\qquad 26+11=37

Therefore the answer is

\boxed{37}

." ::: :::question type="MSQ" question="Which of the following sequences are geometric?" options=["

3,6,12,24,\dots

","

1,-2,4,-8,\dots

","

5,10,15,20,\dots

","

81,27,9,3,\dots

"] answer="A,B,D" hint="Check whether the ratio is constant." solution="1. Ratio is

2

, so geometric.

Ratio is

-2

, so geometric.

Differences are constant, not ratios; this is arithmetic, not geometric.

Ratio is

\dfrac{1}{3}

, so geometric.

Hence the correct answer is

\boxed{A,B,D}

." ::: :::question type="SUB" question="Find the

n

th term of the sequence

1,4,9,16,\dots

and justify your answer." answer="

a_n=n^2

" hint="Recognise the terms as perfect squares." solution="The terms are

\qquad 1=1^2,\ 4=2^2,\ 9=3^2,\ 16=4^2

So the pattern is that the

n

th term equals the square of

n

. Hence,

\qquad a_n=n^2

This matches all given terms, so the required formula is

\boxed{a_n=n^2}

." ::: ---

Summary

❗ Key Takeaways for CMI

Pattern recognition begins with checking differences, ratios, and signs.

Constant first difference suggests a linear rule.

Constant second difference suggests a quadratic rule.

Alternating patterns usually involve powers of $-1$ .

Known patterns such as squares, cubes, and triangular numbers appear frequently.

A good sequence rule must be tested against all known terms, not guessed from one clue.

---

💡 Next Up

Proceeding to Recursively defined sequences.

---

Part 2: Recursively defined sequences

Recursively Defined Sequences

Overview

A recursively defined sequence is one in which later terms are defined using earlier ones. In exam problems, the real skill is not just computing a few terms, but discovering the hidden structure: closed form, monotonicity, boundedness, periodicity, invariants, or a transformed recurrence that becomes easier. CMI-style questions often push beyond standard scalar recurrences and may involve recursive rules for vectors, functions, or algebraic expressions. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Compute terms from a recursive definition correctly.

Recognize first-order, second-order, and nonlinear recurrences.

Convert a recurrence into a simpler one using substitution, differences, ratios, or normalization.

Prove formulas for recursively defined objects using induction.

Handle non-standard recurrences involving vectors, functions, or multi-variable relations.

---

What Is a Recursive Definition?

📖 Recursive Rule

A recursive definition specifies:

one or more initial values, and

a rule that generates later terms from earlier terms.

Example:

\qquad a_1=2,\quad a_{n+1}=3a_n+1

Here every new term depends on the previous term.

❗ Initial Conditions Matter

A recurrence relation alone is usually not enough to determine the sequence uniquely.

For example,
$\qquad a_{n+1}=2a_n$
has many solutions:

$1,2,4,8,\dots$

$3,6,12,24,\dots$

$\dfrac12,1,2,4,\dots$

The initial value fixes which sequence we get.

---

Basic Types of Recurrences

📐 Common Forms

First-order linear

\qquad a_{n+1}=ra_n+c

Homogeneous second-order

\qquad a_{n+2}=pa_{n+1}+qa_n

Nonlinear

\qquad a_{n+1}=a_n^2+1

\qquad a_{n+1}=\dfrac{1}{1+a_n}

Alternating / periodic type

\qquad a_{n+2}=a_n

Recurrence on general objects

vectors, matrices, functions, polynomials

---

First Tool: Compute a Few Terms

💡 Start Small

In a recurrence problem, always compute the first few terms unless the pattern is already obvious.

This often reveals:

periodicity,

sign pattern,

growth,

telescoping structure,

parity behavior,

or a simple closed form.

Example If

\qquad a_1=1,\quad a_{n+1}=a_n+n

then

\qquad a_2=2,\ a_3=4,\ a_4=7,\ a_5=11

The increments are

\qquad 1,2,3,4,\dots

\qquad a_n=1+\sum_{k=1}^{n-1} k = 1+\dfrac{(n-1)n}{2}

---

First-Order Linear Recurrence

📐 Standard Reduction

For
$\qquad a_{n+1}=ra_n+c$

if $r\ne 1$ , shift by the fixed point. Let
$\qquad b_n=a_n-\dfrac{c}{1-r}$

Then
$\qquad b_{n+1}=rb_n$

So
$\qquad b_n=b_1r^{n-1}$

Hence
$\qquad a_n=\left(a_1-\dfrac{c}{1-r}\right)r^{n-1}+\dfrac{c}{1-r}$

Example Solve

\qquad a_1=5,\quad a_{n+1}=2a_n+3

The fixed point is

\qquad \dfrac{3}{1-2}=-3

Let

\qquad b_n=a_n+3

Then

\qquad b_{n+1}=2b_n

Since

\qquad b_1=8

we get

\qquad b_n=8\cdot 2^{n-1}

\qquad a_n=8\cdot 2^{n-1}-3=2^{n+2}-3

---

Telescoping by Differences

📐 Difference Method

If a recurrence is of the form
$\qquad a_{n+1}-a_n=f(n)$

then sum both sides:

$\qquad a_n-a_1=\sum_{k=1}^{n-1} f(k)$

So
$\qquad a_n=a_1+\sum_{k=1}^{n-1} f(k)$

This is one of the fastest methods for recurrences with additive increments. ---

Multiplicative Recurrences

📐 Ratio or Logarithm View

If
$\qquad a_{n+1}=r_na_n$

then
$\qquad a_n=a_1\prod_{k=1}^{n-1} r_k$

If $r_k$ is constant, this becomes a geometric sequence.

Example If

\qquad a_1=3,\quad a_{n+1}=\dfrac{n+1}{n}a_n

then

\qquad a_n=3\prod_{k=1}^{n-1}\dfrac{k+1}{k}=3n

---

Second-Order Recurrences

📐 Characteristic Equation Idea

For a linear homogeneous recurrence
$\qquad a_{n+2}=pa_{n+1}+qa_n$

try a solution of the form
$\qquad a_n=\lambda^n$

Then
$\qquad \lambda^2=p\lambda+q$

This gives the characteristic equation
$\qquad \lambda^2-p\lambda-q=0$

For school-level and early olympiad use, many problems are solved by:

spotting a pattern,

trying small cases,

or transforming the recurrence.

---

Induction and Recursively Defined Sequences

❗ How Closed Forms Are Proved

If you guess a formula for $a_n$ , the usual proof method is induction.

To prove
$\qquad a_n=F(n)$

show:

it works for the initial value,

if it works for $n$ , then the recurrence gives it for $n+1$

This is especially important when the closed form is guessed from computed terms. ---

Monotonicity and Boundedness

📖 Two Very Common Questions

For recursive sequences, many exam problems ask whether the sequence is:

increasing / decreasing,

bounded above / bounded below,

convergent

💡 Typical Route

To show a sequence converges:

prove it is monotone,

prove it is bounded,

then use monotone convergence intuition

Example If

\qquad a_{n+1}=\dfrac{a_n+2}{2}

and

a_1>2

then

\qquad a_{n+1}-2=\dfrac{a_n-2}{2}

So the distance from

2

keeps halving. Hence the sequence decreases to

2

. ---

Periodicity and Invariants

❗ Nonlinear Recurrences Often Hide Invariants

For recurrences that do not look solvable directly, search for:

preserved quantity,

parity pattern,

periodic cycle,

constant norm,

alternating sign behavior,

or reduction to a smaller state space

Example If

\qquad a_{n+2}=a_n

then the entire sequence is determined by

a_1

and

a_2

, and is periodic with period

2

. ---

Recurrences Beyond Numbers

📖 Recursive Objects

Not all recursive problems are about number sequences.

You may see:

vectors:

\qquad v_{n+2}=v_n\times v_{n+1}

functions:

\qquad g(n+m)=g(n)+nm(n+m)+g(m)

sets, matrices, or polynomials

The same core ideas still apply:

compute special cases,

substitute small values,

search for structure,

prove the pattern rigorously.

::: ---

PYQ Insight 1: Recursive Functional Rule on $\mathbb{Z}^+$

❗ 2023-Type Pattern

Suppose
$\qquad g(n+m)=g(n)+nm(n+m)+g(m)$
for all positive integers $m,n$ .

This is not a standard sequence recurrence, but it is still recursive in a discrete sense. The key method is to substitute strategically:

set $m=1$ to get a step-by-step relation for $g(n+1)$

compare different expansions of $g(n+m)$

guess polynomial behavior

prove the exact form by induction or coefficient comparison

A natural candidate is a cubic polynomial, because the extra term

\qquad nm(n+m)=n^2m+nm^2

has total degree

3

.

If we try

\qquad g(n)=an^3+bn^2+cn+d

and substitute, we find that the relation forces

\qquad d=0,\qquad a=\dfrac13,\qquad b=0

while

c

remains free.

So the complete family is

\qquad g(n)=\dfrac13 n^3+cn

for suitable integer-valued choice of

c

if the codomain is

\mathbb{Z}^+

.

This is a typical CMI pattern: a discrete functional recurrence that secretly forces a polynomial.

---

PYQ Insight 2: Vector Recurrence

❗ 2021-Type Pattern

For
$\qquad v_{n+2}=v_n\times v_{n+1}$

the recurrence is nonlinear and vector-valued. Direct closed forms are not the point. Instead, the key tools are:

geometric meaning of cross product,

orthogonality:

\qquad v_n\times v_{n+1}

is perpendicular to both

v_n

and

v_{n+1}

zero vector cases:

cross product becomes zero if two successive vectors become parallel

finite-state or periodic behavior in special examples

So for such recurrences, the right method is not formula memorization, but structural reasoning.

---

Minimal Worked Examples

Example 1 Let

\qquad a_1=2,\quad a_{n+1}=a_n+2n+1

Then

\qquad a_n-a_1=\sum_{k=1}^{n-1} (2k+1)

\qquad a_n=2+\left(n^2-1\right)=n^2+1

--- Example 2 Let

\qquad a_1=1,\quad a_{n+1}=2a_n

Then

\qquad a_n=2^{n-1}

This is the simplest geometric recurrence. ---

Pattern Library

📐 High-Value Patterns

$a_{n+1}-a_n=f(n)$

\rightarrow

sum differences

$a_{n+1}=ra_n$

\rightarrow

geometric

$a_{n+1}=ra_n+c$

\rightarrow

shift by fixed point

$a_{n+1}=\dfrac{\alpha a_n+\beta}{\gamma a_n+\delta}$

\rightarrow

try fixed points or substitution

$a_{n+2}=F(a_n,a_{n+1})$

\rightarrow

compute terms, search for invariant or periodicity

---

CMI Strategy

💡 How to Attack Recursive Sequence Problems

Write down the first few terms.

Identify whether the recurrence is additive, multiplicative, linear, nonlinear, or structural.

Try to simplify by subtraction, ratio, or change of variable.

Guess the pattern only after enough evidence.

Prove the guessed formula by induction.

For unusual recurrences, search for invariants, symmetry, orthogonality, parity, or periodicity.

Do not force a closed form if the problem is really about structure.

---

Common Mistakes

⚠️ Avoid These Errors

❌ Computing terms carelessly and building a wrong pattern

❌ Guessing a formula but not proving it

❌ Ignoring initial conditions

❌ Treating nonlinear recurrences like linear ones

❌ Missing the easiest substitution, such as $m=1$ in a functional recurrence

❌ Expanding everything when the recurrence hides a cleaner invariant

---

Practice Questions

:::question type="MCQ" question="Let

a_1=3

and

a_{n+1}=a_n+2

. Which formula gives

a_n

?" options=["

2n+1

","

2n+3

","

3n

","

n^2+2

"] answer="A" hint="This is an arithmetic progression written recursively." solution="The recurrence adds

2

each time, starting from

a_1=3

. So

\qquad a_n = 3 + 2(n-1)=2n+1

Therefore the correct option is

\boxed{A}

." ::: :::question type="NAT" question="Let

a_1=1

and

a_{n+1}=3a_n+2

. Find

a_2+a_3

." answer="18" hint="Compute the next two terms directly." solution="We compute:

\qquad a_2=3\cdot 1+2=5

Then

\qquad a_3=3\cdot 5+2=17

\qquad a_2+a_3=5+17=22

Hence the answer is

\boxed{22}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["A recursive definition needs initial value information","The recurrence

a_{n+1}=2a_n

determines a unique sequence without any starting value","If

a_{n+1}-a_n=n

, then

a_n=a_1+\sum_{k=1}^{n-1}k

","The recurrence

a_{n+2}=a_n

always produces a periodic sequence"] answer="A,C,D" hint="Think about uniqueness and periodicity." solution="1. True. Initial data are needed to specify the sequence uniquely.

False. Without a starting value, there are infinitely many sequences satisfying

a_{n+1}=2a_n

True. Summing the differences gives

\qquad a_n-a_1=\sum_{k=1}^{n-1} k

True. Since each term repeats two steps later, the sequence is periodic with period dividing

2

Hence the correct answer is

\boxed{A,C,D}

." ::: :::question type="SUB" question="Let

a_1=2

and

a_{n+1}=2a_n+1

. Find a closed form for

a_n

and prove it." answer="

a_n=3\cdot 2^{n-1}-1

" hint="Shift by the fixed point." solution="We are given

\qquad a_{n+1}=2a_n+1,\qquad a_1=2

We look for a constant

L

such that subtracting

L

makes the recurrence homogeneous:

\qquad a_{n+1}-L=2(a_n-L)

This requires

\qquad 2L+1=L

\qquad L=-1

Now define

\qquad b_n=a_n+1

Then

\qquad b_{n+1}=a_{n+1}+1=2a_n+1+1=2(a_n+1)=2b_n

Also

\qquad b_1=a_1+1=3

\qquad b_n=3\cdot 2^{n-1}

Hence

\qquad a_n=b_n-1=3\cdot 2^{n-1}-1

Now prove by induction. Base case:

\qquad a_1=2

and the formula gives

\qquad 3\cdot 2^{0}-1=2

which is correct. Inductive step: Assume

\qquad a_n=3\cdot 2^{n-1}-1

Then

\qquad a_{n+1}=2a_n+1=2\left(3\cdot 2^{n-1}-1\right)+1=3\cdot 2^n-1

So the formula also holds for

n+1

. Therefore

\qquad a_n=\boxed{3\cdot 2^{n-1}-1}

for all

n\ge 1

." ::: ---

Summary

❗ Key Takeaways for CMI

A recursive sequence needs both a rule and initial data.

Many recurrences are solved by transforming them into simpler forms.

Differences, ratios, and fixed-point shifts are standard tools.

Pattern guessing is useful, but proof usually requires induction.

Not every recurrence wants a closed form; some want invariants or structure.

CMI-style recurrences may involve numbers, vectors, or functions on integers.

---

💡 Next Up

Proceeding to Sum formulas.

---

Part 3: Sum formulas

Sum formulas

Overview

Many sequence and series problems become simple once the right sum formula is recognised. In CMI-style questions, direct addition is often too slow; instead, the pattern of the terms must be converted into a known formula or a telescoping structure. This topic focuses on the standard finite sums that appear repeatedly in algebra and pre-calculus. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

use standard formulas for sums of natural numbers, squares, and cubes

find sums of arithmetic and geometric progressions

recognise telescoping and related cancellations

rewrite a complicated sum into standard pieces

solve medium-level exam problems without term-by-term expansion

---

Sigma Notation

📖 Summation notation

The expression

$\qquad \sum_{k=1}^{n} a_k$

means

$\qquad a_1+a_2+\cdots+a_n$

It is a compact way to write finite sums.

📐 Basic linearity

For constants $c$ and sequences $a_k,b_k$ :

$\sum_{k=1}^{n}(a_k+b_k)=\sum_{k=1}^{n}a_k+\sum_{k=1}^{n}b_k$

$\sum_{k=1}^{n} c\,a_k=c\sum_{k=1}^{n}a_k$

---

Standard Sum Formulas

📐 Most important formulas

Sum of first $n$ natural numbers:

\qquad 1+2+\cdots+n=\dfrac{n(n+1)}{2}

Sum of first $n$ squares:

\qquad 1^2+2^2+\cdots+n^2=\dfrac{n(n+1)(2n+1)}{6}

Sum of first $n$ cubes:

\qquad 1^3+2^3+\cdots+n^3=\left(\dfrac{n(n+1)}{2}\right)^2

❗ Beautiful identity

The sum of the first $n$ cubes equals the square of the sum of the first $n$ natural numbers:

$\qquad 1^3+2^3+\cdots+n^3=\big(1+2+\cdots+n\big)^2$

---

Arithmetic Progression Sum

📐 AP sum

If an arithmetic progression has first term $a$ , common difference $d$ , and $n$ terms, then

$\qquad S_n=\dfrac{n}{2}\big[2a+(n-1)d\big]$

Equivalently, if the last term is $\ell$ , then

$\qquad S_n=\dfrac{n}{2}(a+\ell)$

Examples:

$3+7+11+\cdots+39$

$10+8+6+\cdots-4$

---

Geometric Progression Sum

📐 Finite GP sum

If a geometric progression has first term $a$ and common ratio $r\ne 1$ , then

$\qquad S_n=a\dfrac{r^n-1}{r-1}$

Equivalently,

$\qquad S_n=a\dfrac{1-r^n}{1-r}$

r=1

, then

\qquad S_n=na

:::

💡 Choose the cleaner form

use $\dfrac{r^n-1}{r-1}$ when $r>1$

use $\dfrac{1-r^n}{1-r}$ when $|r|<1$ or signs look cleaner

---

Telescoping Sums

📖 Telescoping pattern

A sum telescopes when most intermediate terms cancel after expansion.

Example:
$\qquad \sum_{k=1}^{n}\left(\dfrac{1}{k}-\dfrac{1}{k+1}\right)$

expands as

$\qquad \left(1-\dfrac{1}{2}\right)+\left(\dfrac{1}{2}-\dfrac{1}{3}\right)+\cdots+\left(\dfrac{1}{n}-\dfrac{1}{n+1}\right)$

Everything cancels except the first and last terms.

So the sum is

$\qquad 1-\dfrac{1}{n+1}=\dfrac{n}{n+1}$

---

Breaking Sums into Pieces

📐 Useful decompositions

Many sums can be rewritten using standard formulas.

Examples:

$\qquad \sum_{k=1}^{n}(2k+1)=2\sum_{k=1}^{n}k+\sum_{k=1}^{n}1$

$\qquad \sum_{k=1}^{n}(k^2+3k)=\sum_{k=1}^{n}k^2+3\sum_{k=1}^{n}k$

💡 Standard shortcut

Whenever you see a polynomial in $k$ inside a summation, break it into separate sums of:

constants

$k^2$

$k^3$

---

Minimal Worked Examples

Example 1 Find

\qquad 1+2+\cdots+20

Using the formula,

\qquad \dfrac{20\cdot 21}{2}=210

So the sum is

\boxed{210}

. --- Example 2 Find

\qquad 3+6+12+24+48

This is a GP with

\qquad a=3,\ r=2,\ n=5

\qquad S_5=3\dfrac{2^5-1}{2-1}=3(32-1)=93

Hence the sum is

\boxed{93}

. --- Example 3 Find

\qquad \sum_{k=1}^{n}\left(\dfrac{1}{k}-\dfrac{1}{k+1}\right)

This is telescoping, so

\qquad S_n=1-\dfrac{1}{n+1}=\dfrac{n}{n+1}

---

Common Pattern Sums

📐 Sums worth knowing quickly

first $n$ odd numbers:

\qquad 1+3+5+\cdots+(2n-1)=n^2

first $n$ even numbers:

\qquad 2+4+6+\cdots+2n=n(n+1)

AP sum:

\qquad \dfrac{n}{2}(a+\ell)

GP sum:

\qquad a\dfrac{r^n-1}{r-1}

for

r\ne 1

---

Common Errors

⚠️ Avoid These Errors

❌ using the GP formula for an AP

❌ forgetting the number of terms

❌ applying the GP formula when $r=1$

❌ expanding a telescoping sum but not cancelling correctly

❌ forgetting that $\sum 1 = n$ , not $1$

❌ using the wrong upper limit in sigma notation

✅ Correct habits:

identify the type of sum first

compute the number of terms carefully

rewrite the sum into standard pieces

check whether cancellation is available

---

CMI Strategy

💡 How to Attack Sum Problems

Identify whether the sum is arithmetic, geometric, polynomial, or telescoping.

Rewrite the summand into standard components.

Use the right closed formula.

For sums with fractions, check for telescoping.

Keep the number of terms under control.

In harder problems, combine pattern recognition with algebraic decomposition.

---

Practice Questions

:::question type="MCQ" question="The value of

1+2+3+\cdots+10

is" options=["

45

","

50

","

55

","

60

"] answer="C" hint="Use the formula for sum of first

n

natural numbers." solution="Using

\qquad 1+2+\cdots+n=\dfrac{n(n+1)}{2}

for

n=10

, we get

\qquad \dfrac{10\cdot 11}{2}=55

Hence the correct option is

\boxed{C}

." ::: :::question type="NAT" question="Find the value of

1^2+2^2+3^2+4^2+5^2

." answer="55" hint="Use the sum of squares formula." solution="Using

\qquad 1^2+2^2+\cdots+n^2=\dfrac{n(n+1)(2n+1)}{6}

for

n=5

, we get

\qquad \dfrac{5\cdot 6\cdot 11}{6}=55

Hence the answer is

\boxed{55}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["

1+3+5+\cdots+(2n-1)=n^2

","

2+4+6+\cdots+2n=n(n+1)

","

1^3+2^3+\cdots+n^3=\left(\dfrac{n(n+1)}{2}\right)^2

","

1+2+\cdots+n=n^2

"] answer="A,B,C" hint="Compare with standard formulas." solution="1. True.

True.

False. The correct formula is

\qquad 1+2+\cdots+n=\dfrac{n(n+1)}{2}

Hence the correct answer is

\boxed{A,B,C}

." ::: :::question type="SUB" question="Find the sum

3+7+11+\cdots+39

." answer="210" hint="This is an arithmetic progression." solution="This is an arithmetic progression with

\qquad a=3,\ d=4,\ \ell=39

First find the number of terms:

\qquad 39=3+(n-1)4

\qquad 36=4(n-1)

\qquad n-1=9

\qquad n=10

Now use the AP sum formula:

\qquad S_n=\dfrac{n}{2}(a+\ell)

\qquad S_{10}=\dfrac{10}{2}(3+39)=5\cdot 42=210

Hence the required sum is

\boxed{210}

." ::: ---

Summary

❗ Key Takeaways for CMI

Learn the standard formulas for sums of $1$ , $k$ , $k^2$ , and $k^3$ .

Identify whether a sum is arithmetic, geometric, or telescoping.

Break complicated sums into standard pieces.

Always track the number of terms carefully.

Telescoping can reduce a long sum to just two surviving terms.

Good sum-solving is mostly pattern recognition plus the right formula.

---

💡 Next Up

Proceeding to Telescoping sums.

---

Part 4: Telescoping sums

Telescoping Sums

Overview

Telescoping sums are sums in which most intermediate terms cancel after expansion, leaving only a few boundary terms. This idea appears in algebraic simplification, sequence problems, partial fractions, inequalities, and recurrence-based expressions. In CMI-style questions, the main skill is not brute-force addition, but recognizing a hidden cancellation pattern. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

identify telescoping structure in finite sums

rewrite terms into cancellation-friendly form

evaluate sums using boundary terms instead of full expansion

use partial fractions to create telescoping patterns

handle shifted-index and difference-form sums carefully

---

Core Idea

📖 Telescoping Sum

A sum is called telescoping if, after writing out a few terms, many consecutive terms cancel and only a small number of initial and final terms remain.

A standard form is

$\qquad \sum_{k=1}^{n}(a_k-a_{k+1})$

Expanding gives

$\qquad (a_1-a_2)+(a_2-a_3)+(a_3-a_4)+\cdots+(a_n-a_{n+1})$

Now everything in the middle cancels, so

$\qquad \sum_{k=1}^{n}(a_k-a_{k+1}) = a_1-a_{n+1}$

❗ Main Recognition Rule

If each term contains two nearby sequence terms with opposite signs, look for telescoping.

---

Fundamental Telescoping Form

📐 Basic Identity

For any sequence $\{a_k\}$ ,

$\qquad \sum_{k=1}^{n}(a_k-a_{k+1}) = a_1-a_{n+1}$

More generally, for integers $r \le n$ ,

$\qquad \sum_{k=r}^{n}(a_k-a_{k+1}) = a_r-a_{n+1}$

---

Common Algebraic Patterns

📐 Difference Form

If a sum can be rewritten as

$\qquad T_k = u_k-u_{k+1}$

then

$\qquad \sum_{k=1}^{n} T_k = u_1-u_{n+1}$

📐 Reciprocal Product Form

A very common telescoping identity is

$\qquad \frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1}$

So

$\qquad \sum_{k=1}^{n}\frac{1}{k(k+1)} =\sum_{k=1}^{n}\left(\frac{1}{k}-\frac{1}{k+1}\right) =1-\frac{1}{n+1} =\frac{n}{n+1}$

📐 Shifted Reciprocal Form

More generally,

$\qquad \frac{1}{k(k+r)}=\frac{1}{r}\left(\frac{1}{k}-\frac{1}{k+r}\right)$

for nonzero $r$ .

This often creates partial telescoping.

---

Why Partial Fractions Matter

❗ Key Algebra Link

Many telescoping sums do not look telescoping at first. They become telescoping only after partial fraction decomposition.

Typical example:

$\qquad \frac{1}{(k+1)(k+2)} = \frac{1}{k+1}-\frac{1}{k+2}$

So the real skill is:

factor the denominator

decompose into simple fractions

check for cancellation across consecutive indices

---

Standard Examples

Example 1 Evaluate

\qquad \sum_{k=1}^{n}\left(\frac{1}{k}-\frac{1}{k+1}\right)

Expanding,

\qquad \left(1-\frac{1}{2}\right)+\left(\frac{1}{2}-\frac{1}{3}\right)+\left(\frac{1}{3}-\frac{1}{4}\right)+\cdots+\left(\frac{1}{n}-\frac{1}{n+1}\right)

Everything cancels except the first and last terms, so

\qquad \sum_{k=1}^{n}\left(\frac{1}{k}-\frac{1}{k+1}\right)=1-\frac{1}{n+1}=\frac{n}{n+1}

--- Example 2 Evaluate

\qquad \sum_{k=1}^{n}\frac{1}{k(k+1)}

Use

\qquad \frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1}

So $\qquad \sum_{k=1}^{n}\frac{1}{k(k+1)} =\sum_{k=1}^{n}\left(\frac{1}{k}-\frac{1}{k+1}\right) =\frac{n}{n+1}$ --- Example 3 Evaluate

\qquad \sum_{k=1}^{n}(k^2-(k-1)^2)

Expand first terms:

\qquad (1^2-0^2)+(2^2-1^2)+(3^2-2^2)+\cdots+(n^2-(n-1)^2)

Everything cancels except

\qquad n^2-0^2=n^2

\qquad \sum_{k=1}^{n}(k^2-(k-1)^2)=n^2

---

Telescoping with Shifted Indices

📐 Index-Shift Pattern

Expressions like

$\qquad \sum_{k=1}^{n}(a_{k+2}-a_k)$

do not fully telescope in the same simple way, but they still simplify after writing initial terms carefully.

Example:

$\qquad (a_3-a_1)+(a_4-a_2)+\cdots+(a_{n+2}-a_n)$

The surviving terms are usually the last shifted terms minus the first unshifted terms.

💡 Practical Rule

When the shift is larger than $1$ , do not jump to a formula too quickly. Write the first few and last few terms explicitly.

---

Product-to-Difference Patterns

📐 Useful Algebraic Conversions

Many sums telescope after using identities such as:

$\dfrac{1}{k(k+1)}=\dfrac{1}{k}-\dfrac{1}{k+1}$

$\dfrac{1}{(k+1)(k+2)}=\dfrac{1}{k+1}-\dfrac{1}{k+2}$

$\dfrac{1}{k(k+2)}=\dfrac{1}{2}\left(\dfrac{1}{k}-\dfrac{1}{k+2}\right)$

$(k+1)^2-k^2=2k+1$

$\sqrt{k+1}-\sqrt{k}=\dfrac{1}{\sqrt{k+1}+\sqrt{k}}$ after rationalization in reverse

---

Finite vs Infinite View

❗ Finite Sum First

In school-level and entrance problems, telescoping is usually used for finite sums.

For infinite sums, first find the finite partial sum $S_n$ , then study the limit:

$\qquad \sum_{k=1}^{\infty}(a_k-a_{k+1}) = \lim_{n\to\infty}(a_1-a_{n+1})$

This is valid only when the limit exists.

---

Boundary-Term Thinking

💡 Best Mental Model

A telescoping sum is usually determined by:

the first surviving term

the last surviving term

So after cancellation, do not look at the middle. Look at the boundaries.

---

Common Traps

⚠️ Avoid These Errors

❌ expanding a long sum without first checking for cancellation pattern

❌ using partial fractions incorrectly

❌ missing index shifts like $k+2$ instead of $k+1$

❌ forgetting boundary terms after cancellation

❌ assuming every rational sum telescopes

❌ cancelling terms that are not actually consecutive matches

---

Recognition Guide

💡 How to Spot Telescoping Quickly

Look for terms of these forms:

$a_k-a_{k+1}$

$\dfrac{1}{k(k+1)}$

$\dfrac{1}{(k+r)(k+s)}$ after partial fractions

$f(k)-f(k-1)$

consecutive numerator-denominator patterns suggesting cancellation

---

CMI Strategy

💡 How to Attack Telescoping Problems

first ask whether the term can be written as a difference

if the term is rational, try partial fractions

write the first three and last three terms before doing anything long

identify what survives after cancellation

keep the final answer in boundary-term form as long as possible

only simplify at the very end

---

Practice Questions

:::question type="MCQ" question="Which of the following sums telescopes directly?" options=["

\sum_{k=1}^{n}(k^2+k)

","

\sum_{k=1}^{n}\left(\dfrac{1}{k}-\dfrac{1}{k+1}\right)

","

\sum_{k=1}^{n}k

","

\sum_{k=1}^{n}(2k+1)

"] answer="B" hint="Look for consecutive cancellation." solution="A telescoping sum has terms that cancel across consecutive indices. The expression

\qquad \sum_{k=1}^{n}\left(\dfrac{1}{k}-\dfrac{1}{k+1}\right)

expands as

\qquad \left(1-\frac{1}{2}\right)+\left(\frac{1}{2}-\frac{1}{3}\right)+\cdots+\left(\frac{1}{n}-\frac{1}{n+1}\right)

and all middle terms cancel. Hence the correct option is

\boxed{B}

." ::: :::question type="NAT" question="Find the value of

\sum_{k=1}^{n}\dfrac{1}{k(k+1)}

." answer="

\dfrac{n}{n+1}

" hint="Use partial fractions." solution="We use

\qquad \dfrac{1}{k(k+1)}=\dfrac{1}{k}-\dfrac{1}{k+1}

Therefore, $\qquad \sum_{k=1}^{n}\dfrac{1}{k(k+1)} =\sum_{k=1}^{n}\left(\dfrac{1}{k}-\dfrac{1}{k+1}\right)$ This becomes

\qquad \left(1-\frac{1}{2}\right)+\left(\frac{1}{2}-\frac{1}{3}\right)+\cdots+\left(\frac{1}{n}-\frac{1}{n+1}\right)

All middle terms cancel, leaving

\qquad 1-\dfrac{1}{n+1}=\dfrac{n}{n+1}

Hence the answer is

\boxed{\dfrac{n}{n+1}}

." ::: :::question type="MSQ" question="Which of the following identities are useful for creating telescoping sums?" options=["

\dfrac{1}{k(k+1)}=\dfrac{1}{k}-\dfrac{1}{k+1}

","

\dfrac{1}{k(k+2)}=\dfrac{1}{2}\left(\dfrac{1}{k}-\dfrac{1}{k+2}\right)

","

k^2-(k-1)^2=2k-1

","

\log(k+1)-\log k = \log\left(\dfrac{k+1}{k}\right)

"] answer="A,B,C,D" hint="Telescoping can come from many difference forms." solution="1. True. This is the standard reciprocal telescoping identity.

True. This creates cancellation with a shift of

2

True. Since

\qquad k^2-(k-1)^2 = k^2-(k^2-2k+1)=2k-1

, this gives a difference form that telescopes when summed appropriately.

True. Differences of logarithms also telescope:

\qquad \sum_{k=1}^{n}(\log(k+1)-\log k)=\log(n+1)-\log 1

Hence all four are useful. Therefore, the answer is

\boxed{A,B,C,D}

." ::: :::question type="SUB" question="Evaluate

\sum_{k=1}^{n}(k^2-(k-1)^2)

." answer="

n^2

" hint="Write the first few terms explicitly." solution="We expand:

\qquad \sum_{k=1}^{n}(k^2-(k-1)^2)

\qquad =(1^2-0^2)+(2^2-1^2)+(3^2-2^2)+\cdots+(n^2-(n-1)^2)

Now all intermediate terms cancel:

$1^2$ cancels

$2^2$ cancels

$3^2$ cancels

and so on

Only the first negative boundary term and the last positive boundary term remain:

\qquad n^2-0^2=n^2

Therefore,

\qquad \sum_{k=1}^{n}(k^2-(k-1)^2)=\boxed{n^2}

." ::: ---

Summary

❗ Key Takeaways for CMI

telescoping sums are controlled by cancellation, not by direct addition

the standard form is $\sum (a_k-a_{k+1})$

partial fractions often reveal hidden telescoping structure

after cancellation, only boundary terms usually survive

writing the first few and last few terms is often the fastest reliable method

index shifts and boundary terms must be handled carefully

---

Chapter Summary

❗ Sums and patterns — Key Points

Pattern Recognition: Skillfully identify arithmetic, geometric, quadratic, and other complex patterns from given sequence terms.
Sequence Definitions: Formulate both explicit and recursive definitions for various types of sequences.
Standard Sum Formulas: Apply established formulas for arithmetic series, geometric series, and sums of powers ( $\sum k$ , $\sum k^2$ , $\sum k^3$ ).
Telescoping Sums: Master the technique of telescoping sums, where intermediate terms cancel, to simplify complex series.
Recurrence Relations: Understand how to derive and solve sums for sequences defined by linear recurrence relations.
Strategic Decomposition: Employ strategic decomposition of terms to facilitate summation or reveal underlying patterns effectively.

---

Chapter Review Questions

:::question type="MCQ" question="A sequence is defined by $a_n = n^2 + n$ . What is the sum of the first 5 terms of this sequence?" options=["50","60","70","80"] answer="70" hint="Calculate the first few terms or use sum formulas for $\sum n^2$ and $\sum n$ ." solution="The terms are $a_1=2, a_2=6, a_3=12, a_4=20, a_5=30$ . Their sum is $2+6+12+20+30=70$ . Alternatively, $\sum_{n=1}^5 (n^2+n) = \sum_{n=1}^5 n^2 + \sum_{n=1}^5 n = \frac{5(5+1)(2 \cdot 5+1)}{6} + \frac{5(5+1)}{2} = \frac{5 \cdot 6 \cdot 11}{6} + \frac{5 \cdot 6}{2} = 55 + 15 = 70$ .
"
:::

:::question type="NAT" question="A sequence is defined by $a_1 = 3$ and $a_n = 2a_{n-1} - 1$ for $n > 1$ . What is the value of $a_4$ ?" answer="17" hint="Calculate the terms iteratively starting from $a_1$ ." solution=" $a_1 = 3$ . $a_2 = 2(3) - 1 = 5$ . $a_3 = 2(5) - 1 = 9$ . $a_4 = 2(9) - 1 = 17$ .
"
:::

:::question type="MCQ" question="Evaluate the sum $\sum_{k=1}^{10} \frac{1}{k(k+1)}$ ." options=[" $\frac{1}{11}$ "," $\frac{10}{11}$ "," $\frac{11}{12}$ ","1"] answer=" $\frac{10}{11}$ " hint="Use partial fraction decomposition to rewrite $\frac{1}{k(k+1)}$ as a difference of two terms, then observe the cancellation." solution="The term $\frac{1}{k(k+1)}$ can be decomposed as $\frac{1}{k} - \frac{1}{k+1}$ .
The sum becomes:

\left(1 - \frac{1}{2}\right) + \left(\frac{1}{2} - \frac{1}{3}\right) + \dots + \left(\frac{1}{10} - \frac{1}{11}\right)

This is a telescoping sum where all intermediate terms cancel out.
The sum simplifies to

1 - \frac{1}{11} = \frac{10}{11}

.
"
:::

:::question type="NAT" question="Find the positive integer $N$ such that $\sum_{k=1}^{N} (2k-1) = 100$ ." answer="10" hint="Recognize the sum of the first $N$ odd integers or use the arithmetic series sum formula." solution="The sum $\sum_{k=1}^{N} (2k-1)$ represents the sum of the first $N$ odd integers. The sum of the first $N$ odd integers is $N^2$ .
Therefore, $N^2 = 100$ .
Since $N$ is a positive integer, $N=10$ .
Alternatively, this is an arithmetic series with $a_1=1$ and common difference $d=2$ . The sum $S_N = \frac{N}{2}(2a_1 + (N-1)d) = \frac{N}{2}(2(1) + (N-1)2) = \frac{N}{2}(2 + 2N - 2) = \frac{N}{2}(2N) = N^2$ .
Setting $N^2 = 100$ , we get $N=10$ .
"
:::

---

What's Next?

💡 Continue Your CMI Journey

The foundational understanding of sequences and sums established in this chapter is indispensable for several advanced topics. It provides essential tools for solving recurrence relations and analyzing polynomial behavior in Algebra, and offers a discrete perspective that will prove invaluable when transitioning to continuous functions and infinite series in Calculus.

Sums and patterns

Sums and patterns

Chapter Contents

| Topic |

Part 1: Pattern recognition in sequences

Pattern recognition in sequences

Overview

Learning Objectives

Core Idea

Arithmetic Pattern

Geometric Pattern

Difference Method

Polynomial Pattern Clues

Alternating Pattern

Recursive Pattern

Minimal Worked Examples

Pattern Building Strategy

Standard Reference Patterns

Common Errors

Practice Questions

Summary

Part 2: Recursively defined sequences

Recursively Defined Sequences

Overview

Learning Objectives

What Is a Recursive Definition?

Basic Types of Recurrences

First Tool: Compute a Few Terms

First-Order Linear Recurrence

Telescoping by Differences

Multiplicative Recurrences

Second-Order Recurrences

Induction and Recursively Defined Sequences

Monotonicity and Boundedness

Periodicity and Invariants

Recurrences Beyond Numbers

PYQ Insight 1: Recursive Functional Rule on Z+\mathbb{Z}^+Z+

PYQ Insight 2: Vector Recurrence

Minimal Worked Examples

Pattern Library

CMI Strategy

Common Mistakes

Practice Questions

Summary

Part 3: Sum formulas

Sum formulas

Overview

Learning Objectives

Sigma Notation

Standard Sum Formulas

Arithmetic Progression Sum

Geometric Progression Sum

Telescoping Sums

Breaking Sums into Pieces

Minimal Worked Examples

Common Pattern Sums

Common Errors

CMI Strategy

Practice Questions

Summary

Part 4: Telescoping sums

Telescoping Sums

Overview

Learning Objectives

Core Idea

Fundamental Telescoping Form

Common Algebraic Patterns

Why Partial Fractions Matter

Standard Examples

Telescoping with Shifted Indices

Product-to-Difference Patterns

Finite vs Infinite View

Boundary-Term Thinking

Common Traps

Recognition Guide

CMI Strategy

Practice Questions

Summary

Chapter Summary

Chapter Review Questions

PYQ Insight 1: Recursive Functional Rule on $\mathbb{Z}^+$