Week 1, Lecture 3: Sequences and Discrete Calculus

🔍 Worked Example: Diagnosing Three Mystery Sequences From Raw Terms

Suppose you are handed three raw lists on an exam and asked to identify their type and determine their closed-form formula for Locker $n$:

1. Mystery Sequence A: $(7, 11, 15, 19, 23, \dots)$
   • Step 1 (Check Differences):
       $c_1 - c_0 = 11 - 7 = 4$
       $c_2 - c_1 = 15 - 11 = 4$
       $c_3 - c_2 = 19 - 15 = 4$
   • Diagnosis: The difference is constant ($a = 4$). This is an Arithmetic Progression.
   • Construct the Formula: Baseline at Locker 0 is $b = 7$. The general term is:
   $$c_n = an + b = 4n + 7 \quad (n \ge 0)$$
2. Mystery Sequence B: $(48, -24, 12, -6, 3, \dots)$
   • Step 1 (Check Differences):
       $c_1 - c_0 = -24 - 48 = -72$
       $c_2 - c_1 = 12 - (-24) = 36$ (Not constant! Not arithmetic.)
   • Step 2 (Check Quotients):
       $\frac{c_1}{c_0} = \frac{-24}{48} = -\frac{1}{2}$
       $\frac{c_2}{c_1} = \frac{12}{-24} = -\frac{1}{2}$
       $\frac{c_3}{c_2} = \frac{-6}{12} = -\frac{1}{2}$
   • Diagnosis: The quotient is constant ($q = -\frac{1}{2}$). This is a Geometric Progression.
   • Construct the Formula: Starting factor at Locker 0 is $a = 48$. The general term is:
   $$c_n = a \cdot q^n = 48 \cdot \left(-\frac{1}{2}\right)^n \quad (n \ge 0)$$
3. Mystery Sequence C (The Trap): $(1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \dots)$
   • Step 1 (Differences): $\frac{1}{2} - 1 = -\frac{1}{2}$, but $\frac{1}{3} - \frac{1}{2} = -\frac{1}{6}$. (Fails arithmetic test.)
   • Step 2 (Quotients): $\frac{1/2}{1} = \frac{1}{2}$, but $\frac{1/3}{1/2} = \frac{2}{3}$. (Fails geometric test.)
   • Diagnosis: Neither! This is the harmonic sequence $c_n = \frac{1}{n+1}$ (or $1/n$ for $n \ge 1$). Knowing when to say "neither" prevents you from forcing the wrong formula onto a problem!

🎯 Worked Example A: The Daily Savings Account (Arithmetic Progression)

Scenario: You start with $\$10$ in a piggy bank on Day 0. Every day thereafter, you deposit $\$3$. Let $c_n$ be your savings on Day $n$.

1. Identify the parameters:
   • Base starting amount: $b = 10$ (the value in Locker 0: $c_0 = 10$).
   • Step size added daily: $a = 3$ (common difference).
2. Write the general formula:
   $$c_n = an + b = 3n + 10$$
3. Compute the first few terms by hand:
   • Day 0: $c_0 = 3(0) + 10 = 10$
   • Day 1: $c_1 = 3(1) + 10 = 13$ (notice: $10 + 3 = 13$)
   • Day 2: $c_2 = 3(2) + 10 = 16$ (notice: $13 + 3 = 16$)
   • Day 3: $c_3 = 3(3) + 10 = 19$
   The sequence is $(10, 13, 16, 19, \dots)$.
4. Jump directly to the future without counting step-by-step:
   How much money will you have on Day 50?
   You don't need to add 3 fifty times! Just plug in $n = 50$:
   $$c_{50} = 3(50) + 10 = 150 + 10 = \$160$$

🎯 Worked Example B: Half-Life Decay (Geometric Progression)

Scenario: A sample contains $80\text{ grams}$ of a substance. Each hour, exactly half of the remaining substance decays. Let $c_n$ be the mass remaining after $n$ hours.

1. Identify the parameters:
   • Starting factor: $a = 80$ (the value in Locker 0: $c_0 = 80$).
   • Multiplier at each hour: $q = \frac{1}{2}$ (common ratio).
2. Write the general formula:
   $$c_n = a \cdot q^n = 80 \cdot \left(\frac{1}{2}\right)^n$$
3. Compute the first few terms by hand:
   • Hour 0: $c_0 = 80 \cdot (1/2)^0 = 80 \cdot 1 = 80\text{ g}$
   • Hour 1: $c_1 = 80 \cdot (1/2)^1 = 40\text{ g}$ (halved once)
   • Hour 2: $c_2 = 80 \cdot (1/2)^2 = 80 \cdot 1/4 = 20\text{ g}$ (halved again)
   • Hour 3: $c_3 = 80 \cdot (1/2)^3 = 80 \cdot 1/8 = 10\text{ g}$
   The sequence is $(80, 40, 20, 10, 5, \dots)$.
4. Jump directly to Hour 6:
   How much remains after 6 hours?
   $$c_6 = 80 \cdot \left(\frac{1}{2}\right)^6 = 80 \cdot \frac{1}{64} = \frac{80}{64} = \frac{5}{4} = 1.25\text{ g}$$

🎯 Exam-Style Worked Examples: Proving Monotonicity Step-by-Step

Example 1 (Using the Difference Test): Prove whether the sequence $a_n = \frac{n}{n + 2}$ for $n \ge 0$ is monotonic.

1. Set up the difference $a_{n+1} - a_n$:
   Substitute $(n+1)$ everywhere you see $n$:
   $$a_{n+1} - a_n = \frac{(n+1)}{(n+1) + 2} - \frac{n}{n + 2} = \frac{n+1}{n+3} - \frac{n}{n+2}$$
2. Find a common denominator and combine:
   The common denominator is $(n+3)(n+2)$:
   $$a_{n+1} - a_n = \frac{(n+1)(n+2) - n(n+3)}{(n+3)(n+2)}$$
   Expand the numerators:
   $$= \frac{(n^2 + 3n + 2) - (n^2 + 3n)}{(n+3)(n+2)} = \frac{2}{(n+3)(n+2)}$$
3. Analyze the sign of the result:
   Since $n \ge 0$, both factors in the denominator are strictly positive, and the numerator is a positive constant ($2 > 0$). Therefore:
   $$a_{n+1} - a_n > 0 \quad \text{for all } n \ge 0$$
   Conclusion: Because the difference is strictly greater than zero, $a_{n+1} > a_n$. The sequence is strictly increasing.

Example 2 (Using the Ratio Test): Prove whether the sequence $b_n = \frac{2^n}{n!}$ is monotonic for $n \ge 1$.

1. Verify positivity:
   For all integers $n \ge 1$, both $2^n > 0$ and $n! > 0$, so $b_n > 0$ (meaning the Ratio Test is safe to apply).
2. Set up the ratio $\frac{b_{n+1}}{b_n}$:
   
   $$\frac{b_{n+1}}{b_n} = \frac{\frac{2^{n+1}}{(n+1)!}}{\frac{2^n}{n!}} = \frac{2^{n+1}}{(n+1)!} \cdot \frac{n!}{2^n}$$
3. Simplify using exponents and factorials:
   Note that $2^{n+1} = 2^n \cdot 2$ and $(n+1)! = (n+1) \cdot n!$:
   $$\frac{b_{n+1}}{b_n} = \frac{2^n \cdot 2}{(n+1) \cdot n!} \cdot \frac{n!}{2^n} = \frac{2}{n+1}$$
4. Compare the quotient to $1$:
   • When $n = 1$: $\frac{2}{1+1} = 1$, which means $b_2 = b_1$ (a flat plateau).
   • For all $n \ge 2$: $\frac{2}{n+1} < 1$, which means $b_{n+1} < b_n$ (strict decrease).
   Conclusion: Because the terms do not strictly drop on the very first step ($b_1 = b_2 = 2$), the sequence is technically weakly decreasing (or non-increasing) for $n \ge 1$, and strictly decreasing for $n \ge 2$.

Example 3 (Strictly Decreasing via Difference Test): Prove whether the sequence $c_n = \frac{1}{n + 1}$ for $n \ge 0$ is monotonic.

1. Set up the difference $c_{n+1} - c_n$:
   Substitute $(n+1)$ everywhere you see $n$:
   $$c_{n+1} - c_n = \frac{1}{(n+1) + 1} - \frac{1}{n + 1} = \frac{1}{n+2} - \frac{1}{n+1}$$
2. Find a common denominator and combine:
   The common denominator is $(n+2)(n+1)$:
   $$c_{n+1} - c_n = \frac{(n+1) - (n+2)}{(n+2)(n+1)} = \frac{n + 1 - n - 2}{(n+2)(n+1)} = \frac{-1}{(n+2)(n+1)}$$
3. Analyze the sign of the result:
   Since $n \ge 0$, the denominator is strictly positive, but the numerator is a negative constant ($-1 < 0$). Therefore:
   $$c_{n+1} - c_n < 0 \quad \text{for all } n \ge 0$$
   Conclusion: Because the difference is strictly less than zero, $c_{n+1} < c_n$. The sequence is strictly decreasing.

Example 4 (Proving Non-Monotonicity): Show that the alternating sequence $d_n = (-1)^n$ for $n \ge 0$ is not monotonic.

1. Examine consecutive differences across steps:
   Compute the difference $d_{n+1} - d_n$ for the first few index steps:
   • From $n=0$ to $n=1$: $d_1 - d_0 = (-1)^1 - (-1)^0 = -1 - 1 = \mathbf{-2}$ (Negative: goes down)
   • From $n=1$ to $n=2$: $d_2 - d_1 = (-1)^2 - (-1)^1 = 1 - (-1) = \mathbf{+2}$ (Positive: goes up)
2. Test the condition across all $n$:
   For a sequence to be monotonic, the derived difference $d_{n+1} - d_n$ must maintain the same sign (either always $\ge 0$ or always $\le 0$) for every single $n$.
3. Analyze the conclusion:
   Because the sign switches back and forth infinitely between negative ($–2$) and positive ($+2$), no single inequality holds for all $n$.
   Conclusion: The sequence changes direction continuously, proving it is non-monotonic.

Example 5 (Proving Non-Monotonicity with Periodic Plateaus): Consider the sequence $(f_n)_{n=0}^\infty$ defined by a repeating 6-step pattern: starting at $f_0 = 0$, it climbs $+1$, holds a flat plateau for two steps, drops $-1$, and holds a flat plateau for two steps, repeating ad infinitum. Prove whether this sequence is monotonic.

1. Write out the explicit terms of the sequence:
   Tracing the cycle step-by-step from $n = 0$ to $n = 7$:
   $f_0 = 0, \quad f_1 = 1, \quad f_2 = 1, \quad f_3 = 1, \quad f_4 = 0, \quad f_5 = 0, \quad f_6 = 0, \quad f_7 = 1$
2. Compute the derived difference sequence $f_n' = f_{n+1} - f_n$:
   Evaluate the change across each consecutive pair of lockers in the first cycle:
   • From $n=0$ to $1$: $f_1 - f_0 = 1 - 0 = \mathbf{+1}$ (Climb)
   • From $n=1$ to $2$: $f_2 - f_1 = 1 - 1 = \mathbf{0}$ (Plateau step 1)
   • From $n=2$ to $3$: $f_3 - f_2 = 1 - 1 = \mathbf{0}$ (Plateau step 2)
   • From $n=3$ to $4$: $f_4 - f_3 = 0 - 1 = \mathbf{-1}$ (Drop)
   • From $n=4$ to $5$: $f_5 - f_4 = 0 - 0 = \mathbf{0}$ (Plateau step 1)
   • From $n=5$ to $6$: $f_6 - f_5 = 0 - 0 = \mathbf{0}$ (Plateau step 2)
3. Analyze the sign pattern across infinity (Periodicity):
   The derived differences form a repeating cycle: $f_n' \in \{+1, 0, 0, -1, 0, 0\}$.
   • Because the difference hits $0$, the sequence contains flat resting plateaus (ruling out strict monotonicity).
   • Because the differences include both positive ($+1$) and negative ($-1$) values, the sequence actively reverses direction.
4. Conclusion:
   Because the derived differences do not maintain a single global sign ($\ge 0$ everywhere or $\le 0$ everywhere), the sequence fails the monotonicity test. It is strictly non-monotonic with periodic flat plateaus.

🎯 Worked Example: Testing Monotonicity and Bounds by Hand

Consider the sequence $a_n = \frac{n}{n+1}$ for $n \ge 0$: $$\left(0, \; \frac{1}{2}, \; \frac{2}{3}, \; \frac{3}{4}, \; \frac{4}{5}, \; \dots\right)$$

1. Step 1: Test Monotonicity using the Difference Method.
   Form the difference $a_{n+1} - a_n$:
   $$a_{n+1} - a_n = \frac{n+1}{(n+1)+1} - \frac{n}{n+1} = \frac{n+1}{n+2} - \frac{n}{n+1}$$
   Find a common denominator:
   $$a_{n+1} - a_n = \frac{(n+1)^2 - n(n+2)}{(n+2)(n+1)} = \frac{(n^2 + 2n + 1) - (n^2 + 2n)}{(n+2)(n+1)} = \frac{1}{(n+2)(n+1)}$$
   Since $n \ge 0$, the numerator is $1 > 0$ and the denominator is strictly positive. Therefore:
   $$a_{n+1} - a_n > 0 \quad \text{for all } n \in \mathbb{N}$$
   Conclusion: The sequence is strictly increasing.
2. Step 2: Establish Bounds.
   • Lower Bound: Because the sequence is strictly increasing, its very first term is its minimum: $a_0 = \frac{0}{0+1} = 0$. Thus, $a_n \ge 0$ for all $n$ (bounded below by $0$).
   • Upper Bound: For every natural number $n$, the numerator $n$ is strictly less than the denominator $n+1$. Therefore:
   $$a_n = \frac{n}{n+1} < 1 \quad \text{for all } n$$
   Thus, the sequence is bounded above by $1$.
   Conclusion: The sequence is bounded because all infinite terms live trapped inside $$0 \le a_n < 1$$

🎯 Worked Example: Scaling and Difference

Suppose you want to scale a sequence by a constant factor and subtract another sequence from it. Let $u_n = n + 2$ and $v_n = 2n$ for $n \ge 0$. Find the general formula and the first four terms of $w_n = (3u - v)_n$:

1. Apply scalar multiplication and subtraction pointwise:
   $$w_n = 3u_n - v_n = 3(n + 2) - 2n = 3n + 6 - 2n = n + 6$$
2. Compute the first few terms by hand:
   • At $n = 0$: $w_0 = 3(2) - 0 = 6$
   • At $n = 1$: $w_1 = 3(3) - 2 = 7$
   • At $n = 2$: $w_2 = 3(4) - 4 = 8$
   • At $n = 3$: $w_3 = 3(5) - 6 = 9$
   Result: $w = (6, 7, 8, 9, \dots)$. Notice how the linear combination of two arithmetic sequences yields another arithmetic sequence with common difference $a = 1$.

🎯 Derivation 1: The Gaussian Sum $\sum_{k=1}^n k$ via Telescoping

We want to find a formula for adding the first $n$ integers: $1 + 2 + 3 + \dots + n$.

1. Look for a sequence whose difference is $k$. Consider $a_k = \frac{k(k-1)}{2} = \frac{k^2 - k}{2}$.
2. Compute its derived difference:
   $$a_k' = a_{k+1} - a_k = \frac{(k+1)k}{2} - \frac{k(k-1)}{2} = \frac{k^2 + k - (k^2 - k)}{2} = \frac{2k}{2} = k$$
3. Because $a_k' = k$, the sum of integers is a telescoping sum:
   $$\sum_{k=1}^n k = \sum_{k=1}^n a_k' = a_{n+1} - a_1$$
4. Evaluate at the endpoints: $a_1 = \frac{1(0)}{2} = 0$, and $a_{n+1} = \frac{(n+1)n}{2}$.
5. The sum collapses immediately to the celebrated Gaussian Summation Formula:
   $$\sum_{k=1}^n k = 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$$

🎯 Derivation 2: The Geometric Series Sum $\sum_{k=0}^{n-1} q^k$ via Telescoping

We want to find the sum of powers of ratio $q$ ($q \ne 1$): $$s_{n-1} = 1 + q + q^2 + q^3 + \dots + q^{n-1} = \sum_{k=0}^{n-1} q^k$$

1. From Section 6, the difference of $(q^k)$ is $(q-1)q^k$.
2. Dividing by the constant scalar $(q-1)$, define the sequence:
   $$a_k = \frac{q^k}{q - 1}$$
3. Check its difference:
   $$a_k' = a_{k+1} - a_k = \frac{q^{k+1} - q^k}{q - 1} = \frac{q^k(q - 1)}{q - 1} = q^k$$
4. Because $a_k' = q^k$, the sum collapses telescopically:
   $$\sum_{k=0}^{n-1} q^k = \sum_{k=0}^{n-1} a_k' = a_n - a_0 = \frac{q^n}{q - 1} - \frac{q^0}{q - 1} = \frac{q^n - 1}{q - 1}$$
5. Multiplying numerator and denominator by $-1$ gives the classic Geometric Series Identity:
   $$\sum_{k=0}^{n-1} q^k = \frac{1 - q^n}{1 - q} \quad (q \ne 1)$$