Chapter 13 — Sequences, Probability, and Counting Theory
How much money will you have in 30 years if you invest monthly? How many ways can a committee be formed? What are the odds of winning a lottery? This chapter covers the mathematics of sequences and series for modeling growth patterns, counting principles for systematic enumeration, the Binomial Theorem for expanding powers, and the fundamentals of probability.
Table of Contents
1 — Sequences and Their Notations
2 — Arithmetic Sequences
3 — Geometric Sequences
4 — Series and Their Notations
5 — Counting Principles
- 5.1 The Multiplication Principle
- 5.2 Permutations
- 5.3 Combinations
- 5.4 Permutations vs. Combinations
6 — Binomial Theorem
7 — Probability
Glossary
| Term | Definition |
|---|---|
| Sequence | An ordered list of numbers following a pattern |
| Term | An individual element $a_n$ of a sequence |
| Series | The sum of the terms of a sequence |
| Arithmetic sequence | Constant difference between consecutive terms |
| Geometric sequence | Constant ratio between consecutive terms |
| $n!$ (factorial) | $n! = n(n-1)(n-2)\cdots 2 \cdot 1$; by convention $0! = 1$ |
| Permutation | Ordered arrangement: $P(n,r) = \dfrac{n!}{(n-r)!}$ |
| Combination | Unordered selection: $\dbinom{n}{r} = \dfrac{n!}{r!(n-r)!}$ |
| Sample space | Set of all possible outcomes |
| Event | A subset of the sample space |
1 — Sequences and Their Notations
1.1 Sequences as Functions
A sequence is a function whose domain is the positive integers (or natural numbers starting at 0 or 1):
\[a_1, a_2, a_3, \ldots, a_n, \ldots\]$a_n$ is the $n$th term (general term).
1.2 Explicit Formulas
An explicit formula gives $a_n$ directly in terms of $n$.
$a_n = 3n + 1$: the sequence is $4, 7, 10, 13, \ldots$
$a_n = (-1)^n \cdot n^2$: the sequence is $-1, 4, -9, 16, \ldots$
1.3 Recursive Formulas
A recursive formula defines each term in terms of previous terms, plus an initial condition.
Fibonacci sequence: $a_1 = 1$, $a_2 = 1$, $a_n = a_{n-1} + a_{n-2}$ for $n \ge 3$.
Sequence: $1, 1, 2, 3, 5, 8, 13, 21, \ldots$
1.4 Factorial Notation
Special cases: $0! = 1$, $1! = 1$.
| $n$ | $n!$ | |—–|——| | 0 | 1 | | 1 | 1 | | 2 | 2 | | 3 | 6 | | 4 | 24 | | 5 | 120 | | 6 | 720 | | 7 | 5040 | | 10 | 3,628,800 |
2 — Arithmetic Sequences
2.1 Common Difference
An arithmetic sequence has a constant common difference $d$:
\[d = a_{n+1} - a_n\]Each term is $d$ more than the previous. If $d > 0$, the sequence increases; if $d < 0$, it decreases.
2.2 The nth Term Formula
Alternate: $a_n = a_m + (n - m)d$ (from any known term $a_m$).
Find $a_{20}$ for the sequence $5, 9, 13, 17, \ldots$
$d = 4$, $a_1 = 5$.
$a_{20} = 5 + 19(4) = 5 + 76 = 81$
2.3 Arithmetic Series
The sum of the first $n$ terms of an arithmetic sequence:
\[S_n = \frac{n}{2}(a_1 + a_n) = \frac{n}{2}[2a_1 + (n-1)d]\]Gauss’s insight: Pair the first and last term, second and second-to-last, etc. — each pair sums to $a_1 + a_n$.
Sum of $1 + 2 + 3 + \cdots + 100$:
$S_{100} = \dfrac{100}{2}(1 + 100) = 50 \cdot 101 = 5050$
3 — Geometric Sequences
3.1 Common Ratio
A geometric sequence has a constant common ratio $r$:
\[r = \frac{a_{n+1}}{a_n}\]Each term is $r$ times the previous.
3.2 The nth Term Formula
\(a_n = a_1 \cdot r^{n-1}\)
Find $a_8$ for the sequence $3, 6, 12, 24, \ldots$
$r = 2$, $a_1 = 3$.
$a_8 = 3 \cdot 2^7 = 3 \cdot 128 = 384$
3.3 Finite Geometric Series
\(S_n = a_1 \cdot \frac{1 - r^n}{1 - r} \qquad (r \ne 1)\)
Sum: $2 + 6 + 18 + 54 + \cdots$ (8 terms).
$a_1 = 2$, $r = 3$, $n = 8$.
$S_8 = 2 \cdot \dfrac{1 - 3^8}{1 - 3} = 2 \cdot \dfrac{1 - 6561}{-2} = 2 \cdot \dfrac{-6560}{-2} = 6560$
3.4 Infinite Geometric Series
| If $ | r | < 1$, the infinite geometric series converges: |
If $|r| \ge 1$, the series diverges (no finite sum).
Sum: $1 + \dfrac{1}{2} + \dfrac{1}{4} + \dfrac{1}{8} + \cdots$
| $a_1 = 1$, $r = \dfrac{1}{2}$. $ | r | < 1$, so: |
$S = \dfrac{1}{1 - 1/2} = \dfrac{1}{1/2} = 2$
Convert the repeating decimal $0.\overline{36}$ to a fraction.
$0.363636\ldots = \dfrac{36}{100} + \dfrac{36}{10000} + \cdots$
$a_1 = \dfrac{36}{100}$, $r = \dfrac{1}{100}$.
$S = \dfrac{36/100}{1 - 1/100} = \dfrac{36/100}{99/100} = \dfrac{36}{99} = \dfrac{4}{11}$
4 — Series and Their Notations
4.1 Summation (Sigma) Notation
$k$ is the index of summation, $1$ is the lower limit, $n$ is the upper limit.
4.2 Properties of Sums
Useful closed forms:
\(\sum_{k=1}^{n} k = \frac{n(n+1)}{2} \qquad \sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6} \qquad \sum_{k=1}^{n} k^3 = \left[\frac{n(n+1)}{2}\right]^2\)
5 — Counting Principles
5.1 The Multiplication Principle
If event $A$ can occur in $m$ ways and event $B$ can occur in $n$ ways, then $A$ and $B$ can occur in $m \times n$ ways (assuming independence).
A restaurant offers 4 appetizers, 6 entrees, and 3 desserts. How many different 3-course meals are possible?
$4 \times 6 \times 3 = 72$ meals.
5.2 Permutations
A permutation is an ordered arrangement of $r$ objects chosen from $n$ distinct objects:
\[P(n, r) = \frac{n!}{(n - r)!}\]Special case: $P(n, n) = n!$ (arrange all $n$ objects).
How many ways can a president, VP, and secretary be chosen from 10 people?
$P(10, 3) = \dfrac{10!}{7!} = 10 \times 9 \times 8 = 720$
Permutations with repetition: If $n$ objects have $n_1$ of type 1, $n_2$ of type 2, etc.:
\(\frac{n!}{n_1!\, n_2!\, \cdots\, n_k!}\)
How many distinguishable arrangements of the letters in MISSISSIPPI?
$M:1$, $I:4$, $S:4$, $P:2$. Total: $11$ letters.
$\dfrac{11!}{1!\, 4!\, 4!\, 2!} = \dfrac{39916800}{1 \cdot 24 \cdot 24 \cdot 2} = 34650$
5.3 Combinations
A combination is an unordered selection of $r$ objects from $n$:
\(\binom{n}{r} = C(n, r) = \frac{n!}{r!(n - r)!}\)
Choose a committee of 3 from 10 people.
$\dbinom{10}{3} = \dfrac{10!}{3! \cdot 7!} = \dfrac{10 \cdot 9 \cdot 8}{6} = 120$
5.4 Permutations vs. Combinations
| Question | Order matters? | Use |
|---|---|---|
| Arrange 3 books on a shelf | Yes | Permutation |
| Choose 3 books to read | No | Combination |
| Create a 4-digit PIN | Yes | Permutation |
| Select 5 cards from a deck | No | Combination |
Ask yourself: Does rearranging the selection create a different outcome? If yes → permutation. If no → combination.
6 — Binomial Theorem
6.1 Pascal’s Triangle
Each row of Pascal’s Triangle gives the binomial coefficients $\dbinom{n}{k}$:
Row 0: 1
Row 1: 1 1
Row 2: 1 2 1
Row 3: 1 3 3 1
Row 4: 1 4 6 4 1
Row 5: 1 5 10 10 5 1
Each entry is the sum of the two entries above it.
6.2 The Binomial Theorem
\(= \binom{n}{0}a^n + \binom{n}{1}a^{n-1}b + \binom{n}{2}a^{n-2}b^2 + \cdots + \binom{n}{n}b^n\)
Expand $(x + 2)^4$.
$= \dbinom{4}{0}x^4(2)^0 + \dbinom{4}{1}x^3(2)^1 + \dbinom{4}{2}x^2(2)^2 + \dbinom{4}{3}x^1(2)^3 + \dbinom{4}{4}x^0(2)^4$
$= x^4 + 4 \cdot 2x^3 + 6 \cdot 4x^2 + 4 \cdot 8x + 16$
$= x^4 + 8x^3 + 24x^2 + 32x + 16$
6.3 Finding a Specific Term
The $(k+1)$th term in the expansion of $(a + b)^n$ is:
\(T_{k+1} = \binom{n}{k} a^{n-k} b^k\)
Find the 4th term of $(3x - 2)^7$.
$k = 3$ (for the 4th term):
$T_4 = \dbinom{7}{3}(3x)^4(-2)^3 = 35 \cdot 81x^4 \cdot (-8) = -22680x^4$
7 — Probability
7.1 Basic Definitions
Experiment: A process with uncertain outcomes (e.g., rolling a die).
Sample space ($S$): Set of all possible outcomes.
Event ($E$): A subset of $S$.
Probability (equally likely outcomes):
\[P(E) = \frac{|E|}{|S|} = \frac{\text{favorable outcomes}}{\text{total outcomes}}\]$0 \le P(E) \le 1$. $P(\emptyset) = 0$. $P(S) = 1$.
7.2 Probability of Complementary Events
where $E’$ (or $\bar{E}$) is the complement — everything not in $E$.
Probability of NOT rolling a 6 on a standard die:
$P(\text{not } 6) = 1 - \dfrac{1}{6} = \dfrac{5}{6}$
7.3 Probability of Unions
Addition Rule:
\[P(A \cup B) = P(A) + P(B) - P(A \cap B)\]If $A$ and $B$ are mutually exclusive ($A \cap B = \emptyset$):
\(P(A \cup B) = P(A) + P(B)\)
A card is drawn from a standard 52-card deck. What is $P(\text{king or heart})$?
$P(K) = \dfrac{4}{52}$, $P(H) = \dfrac{13}{52}$, $P(K \cap H) = \dfrac{1}{52}$ (king of hearts).
$P(K \cup H) = \dfrac{4}{52} + \dfrac{13}{52} - \dfrac{1}{52} = \dfrac{16}{52} = \dfrac{4}{13}$
7.4 Independent Events and Conditional Probability
Independent events: The occurrence of one does not affect the other.
\[P(A \cap B) = P(A) \cdot P(B) \quad \text{(if independent)}\]Conditional probability:
\[P(A \mid B) = \frac{P(A \cap B)}{P(B)}\]“The probability of $A$ given that $B$ has occurred.”
Two dice are rolled. What is the probability both show 6?
$P(6 \text{ on first}) = \dfrac{1}{6}$, $P(6 \text{ on second}) = \dfrac{1}{6}$.
Independent: $P(\text{both}) = \dfrac{1}{6} \cdot \dfrac{1}{6} = \dfrac{1}{36}$
Key Takeaways
- Arithmetic sequences: $a_n = a_1 + (n-1)d$; sum $S_n = \dfrac{n}{2}(a_1 + a_n)$.
-
Geometric sequences: $a_n = a_1 r^{n-1}$; finite sum $S_n = a_1\dfrac{1 - r^n}{1 - r}$; infinite sum $S = \dfrac{a_1}{1 - r}$ when $ r < 1$. - Factorial: $n! = n(n-1)\cdots 1$; $0! = 1$.
- Permutations (order matters): $P(n,r) = \dfrac{n!}{(n-r)!}$.
- Combinations (order doesn’t): $\dbinom{n}{r} = \dfrac{n!}{r!(n-r)!}$.
- Binomial Theorem: $(a+b)^n = \sum \dbinom{n}{k}a^{n-k}b^k$.
-
Probability basics: $P(E) = E / S $; complement $P(E’) = 1 - P(E)$; addition rule for unions. - Independent events multiply; use conditional probability when events are dependent.
- Repeating decimals convert to fractions via infinite geometric series.
Practice Questions
Q1. Find the 15th term of the arithmetic sequence $7, 11, 15, 19, \ldots$
Answer:
$d = 4$, $a_1 = 7$.
$a_{15} = 7 + 14(4) = 7 + 56 = 63$
Q2. Find $S_{10}$ for the arithmetic series $3 + 7 + 11 + 15 + \cdots$
Answer:
$d = 4$, $a_1 = 3$, $a_{10} = 3 + 9(4) = 39$.
$S_{10} = \dfrac{10}{2}(3 + 39) = 5 \cdot 42 = 210$
Q3. Find the sum of the infinite geometric series $27 + 9 + 3 + 1 + \cdots$
Answer:
$a_1 = 27$, $r = \dfrac{1}{3}$.
$S = \dfrac{27}{1 - 1/3} = \dfrac{27}{2/3} = \dfrac{81}{2} = 40.5$
Q4. How many arrangements of the letters in BANANA are there?
Answer:
$B:1$, $A:3$, $N:2$. Total: $6$ letters.
$\dfrac{6!}{1! \cdot 3! \cdot 2!} = \dfrac{720}{12} = 60$
Q5. Find the coefficient of $x^3$ in $(2x - 1)^5$.
Answer:
The term with $x^3$ has $k = 2$ (since $a = 2x$, $b = -1$, $n - k = 3 \Rightarrow k = 2$):
$T_3 = \dbinom{5}{2}(2x)^3(-1)^2 = 10 \cdot 8x^3 \cdot 1 = 80x^3$
Coefficient: $80$
Q6. A bag has 5 red, 3 blue, and 2 green marbles. Two marbles are drawn without replacement. What is the probability both are red?
Answer:
$P(\text{1st red}) = \dfrac{5}{10} = \dfrac{1}{2}$
$P(\text{2nd red} \mid \text{1st red}) = \dfrac{4}{9}$
$P(\text{both red}) = \dfrac{1}{2} \cdot \dfrac{4}{9} = \dfrac{4}{18} = \dfrac{2}{9}$
Q7. A committee of 4 must be chosen from 6 men and 8 women. How many committees have exactly 2 men and 2 women?
Answer:
$\dbinom{6}{2} \cdot \dbinom{8}{2} = 15 \cdot 28 = 420$