Sequences, Series & Recursion

Study Sheet

Sequences, Series & Recursion

Sums, telescoping, and recurrences

Standard Sums

Tip
Arithmetic and geometric series

Arithmetic: Sn=n2(a1+an)S_n = \tfrac n2(a_1+a_n). Geometric: Sn=a11−rn1−rS_n = a_1\dfrac{1-r^n}{1-r}, and if ∣r∣<1|r|<1, S∞=a11−rS_\infty = \dfrac{a_1}{1-r}.

In plain terms. For a steadily-growing list use the arithmetic sum; for one that multiplies each step use the geometric sum.

Example. 1+12+14+⋯=11−1/2=21 + \tfrac12 + \tfrac14 + \cdots = \dfrac{1}{1 - 1/2} = 2.

Why they hold. Write an arithmetic series forwards and backwards and add: every column is a1+ana_1 + a_n, and there are nn columns, so 2Sn=n(a1+an)2S_n = n(a_1 + a_n). For a geometric series, Sn−rSn=a1−a1rnS_n - rS_n = a_1 - a_1r^n because every middle term appears in both and cancels. When ∣r∣<1|r| < 1 the term rnr^n shrinks to 00, which gives the infinite sum; when ∣r∣≥1|r| \ge 1 it does not, and there is no finite sum.

Concept
Telescoping

If each term is f(k)−f(k+1)f(k) - f(k+1), the sum collapses to f(1)−f(n+1)f(1) - f(n+1).

In plain terms. Write each piece as a difference so neighboring pieces cancel, leaving only the first and last.

Example. ∑k=1n1k(k+1)=∑(1k−1k+1)=1−1n+1\sum_{k=1}^{n}\tfrac1{k(k+1)} = \sum\left(\tfrac1k - \tfrac1{k+1}\right) = 1 - \tfrac1{n+1}.

Example
Worked: two partial sums fix the sequence

The first 1010 terms of an arithmetic sequence add to 100100 and the first 2020 terms add to 400400. What do the first 3030 terms add to?

Spotting it. Two sums give two linear equations in the first term aa and the difference dd.

Step 1. S10=102(2a+9d)=100S_{10} = \tfrac{10}{2}(2a + 9d) = 100 and S20=202(2a+19d)=400S_{20} = \tfrac{20}{2}(2a + 19d) = 400, so 2a+9d=202a + 9d = 20 and 2a+19d=402a + 19d = 40.

Step 2. Subtract: 10d=2010d = 20, so d=2d = 2 and a=1a = 1. The sequence is 1,3,5,…1, 3, 5, \dots, the odd numbers.

Step 3. S30=15(2+58)=900S_{30} = 15(2 + 58) = 900. (The sum of the first nn odd numbers is n2n^2 ✓)

Example
Worked: a geometric series and its squares

An infinite geometric series has sum 1212, and the series of the squares of its terms has sum 4848. Find the first term.

Spotting it. Squaring each term of a geometric series gives another geometric series, with first term a2a^2 and ratio r2r^2. Dividing the two sum formulas cancels most of the unknowns.

Step 1. a1−r=12\dfrac{a}{1 - r} = 12 and a21−r2=48\dfrac{a^2}{1 - r^2} = 48.

Step 2. Divide the second by the first, using 1−r2=(1−r)(1+r)1 - r^2 = (1 - r)(1 + r): a1+r=4\dfrac{a}{1 + r} = 4.

Step 3. So 12(1−r)=4(1+r)12(1 - r) = 4(1 + r), giving r=12r = \tfrac12 and a=6a = 6. Check: 6+3+32+⋯=126 + 3 + \tfrac32 + \cdots = 12 and 36+9+94+⋯=363/4=4836 + 9 + \tfrac94 + \cdots = \tfrac{36}{3/4} = 48 ✓

Example
Worked: an arithmetic-times-geometric sum

Evaluate ∑n=1∞n2n=12+24+38+⋯\displaystyle\sum_{n=1}^{\infty}\frac{n}{2^n} = \frac12 + \frac24 + \frac38 + \cdots.

Spotting it. The numerators grow arithmetically and the denominators geometrically. The geometric-series proof (shift and subtract) still works, and it turns this series into a plain geometric one.

Step 1. S=12+24+38+⋯S = \tfrac12 + \tfrac24 + \tfrac38 + \cdots and 12S=14+28+316+⋯\tfrac12S = \tfrac14 + \tfrac28 + \tfrac{3}{16} + \cdots.

Step 2. Subtract term by term: S−12S=12+14+18+⋯=1S - \tfrac12S = \tfrac12 + \tfrac14 + \tfrac18 + \cdots = 1.

Step 3. So 12S=1\tfrac12S = 1 and S=2S = 2.

Side note
Where it goes wrong

Counting terms. 5,8,11,…,355, 8, 11, \dots, 35 has 35−53+1=11\tfrac{35 - 5}{3} + 1 = 11 terms, not 1010: dividing the span by the step counts the GAPS, and there is one more term than gaps. The same off-by-one hides in "the multiples of 77 from 105105 to 497497".

Try it
Try it: multiples of 7

Find the sum of all multiples of 77 between 100100 and 500500.

Show the answer

The multiples run from 105=7⋅15105 = 7 \cdot 15 to 497=7⋅71497 = 7 \cdot 71, so there are 71−15+1=5771 - 15 + 1 = 57 of them. The sum is 572(105+497)=57⋅301=17157\tfrac{57}{2}(105 + 497) = 57 \cdot 301 = 17157.

Telescoping and Infinite Series

Tip
Telescoping sums

Write each term as a difference: if tk=uk−uk+1t_k = u_k - u_{k+1} then ∑k=1ntk=u1−un+1\sum_{k=1}^n t_k = u_1 - u_{n+1}.

The standard case is 1k(k+1)=1k−1k+1\dfrac{1}{k(k+1)} = \dfrac1k - \dfrac1{k+1}, so ∑k=1n1k(k+1)=1−1n+1=nn+1\sum_{k=1}^{n}\dfrac{1}{k(k+1)} = 1 - \dfrac{1}{n+1} = \dfrac{n}{n+1}. Partial fractions is how the difference is FOUND; recognising that a sum should telescope usually comes from seeing consecutive-looking denominators.

Tip
Geometric series, finite and infinite
1/41/16
In each L-shape one of three equal squares is shaded, so the shaded total 14+116+⋯\tfrac14 + \tfrac1{16} + \cdots is one third of the square.

∑k=0n−1ark=a1−rn1−r\sum_{k=0}^{n-1} ar^k = a\dfrac{1-r^n}{1-r}, and for ∣r∣<1|r| < 1, ∑k=0∞ark=a1−r\sum_{k=0}^{\infty} ar^k = \dfrac{a}{1-r}.

Repeating decimals are geometric series: 0.27‾=27/1001−1/100=2799=3110.\overline{27} = \dfrac{27/100}{1 - 1/100} = \dfrac{27}{99} = \dfrac{3}{11}. The convergence condition is not decoration — a contest answer of a1−r\tfrac{a}{1-r} with ∣r∣≥1|r| \ge 1 is a wrong answer, and checking ∣r∣<1|r| < 1 takes one glance.

Example
Worked: a telescoping sum

Compute ∑k=1991k(k+1)\displaystyle\sum_{k=1}^{99}\frac{1}{k(k+1)}.

Step 1 — partial fractions: 1k(k+1)=1k−1k+1\dfrac{1}{k(k+1)} = \dfrac1k - \dfrac1{k+1}.

Step 2 — the sum collapses: (1−12)+(12−13)+⋯+(199−1100)=1−1100\left(1 - \tfrac12\right) + \left(\tfrac12 - \tfrac13\right) + \cdots + \left(\tfrac1{99} - \tfrac1{100}\right) = 1 - \tfrac1{100}.

Step 3 — =99100= \dfrac{99}{100}.

Example
Worked: an infinite telescope in disguise

Evaluate ∑n=1∞2n+1n2(n+1)2\displaystyle\sum_{n=1}^{\infty}\frac{2n + 1}{n^2(n + 1)^2}.

Spotting it. The denominator is a product of consecutive squares, and the numerator 2n+12n + 1 is exactly their difference: (n+1)2−n2=2n+1(n + 1)^2 - n^2 = 2n + 1.

Step 1. 2n+1n2(n+1)2=(n+1)2−n2n2(n+1)2=1n2−1(n+1)2\dfrac{2n + 1}{n^2(n + 1)^2} = \dfrac{(n + 1)^2 - n^2}{n^2(n + 1)^2} = \dfrac{1}{n^2} - \dfrac{1}{(n + 1)^2}.

Step 2. The partial sums telescope to 1−1(N+1)21 - \dfrac{1}{(N + 1)^2}, which tends to 11. The sum is 11.

Side note
Where it goes wrong

Telescoping an infinite sum whose leftover does not vanish. ∑k=1N(k+1−k)=N+1−1\sum_{k=1}^{N}\left(\sqrt{k + 1} - \sqrt k\right) = \sqrt{N + 1} - 1, which grows without bound, so the infinite series has no sum even though "everything cancels". An infinite telescope ∑(uk−uk+1)\sum(u_k - u_{k+1}) converges to u1−lim⁡uku_1 - \lim u_k only when that limit exists; check it.

Try it
Try it: an infinite series

Evaluate 34+316+364+⋯\dfrac34 + \dfrac{3}{16} + \dfrac{3}{64} + \cdots.

Show the answer

Geometric with a=34a = \tfrac34, r=14r = \tfrac14: sum =3/43/4=1= \dfrac{3/4}{3/4} = 1.

Recursions That Repeat

Tip
Compute terms until the sequence repeats

For a nonlinear recursion, compute the first several terms and look for a repeat. If each term is determined by the previous kk terms, then as soon as kk CONSECUTIVE terms reappear, the whole sequence repeats with that period from then on.

Why it works. The recursion is a machine that turns the last kk terms into the next one. If the machine is fed the same kk terms twice, it produces the same continuation twice, forever. So a period is proved the moment a full window of kk consecutive terms repeats. Then the nnth term depends only on nn modulo the period, and sums over whole periods can be computed once.

Example
Worked: a ratio recursion

a1=2a_1 = 2, a2=3a_2 = 3 and an=an−1an−2a_n = \dfrac{a_{n-1}}{a_{n-2}} for n≥3n \ge 3. Find a2026a_{2026} and the product a1a2⋯a2026a_1a_2\cdots a_{2026}.

Spotting it. No formula suggests itself, so compute: division recursions like this one tend to cycle.

Step 1. 2,3,32,12,13,23,2,3,…2, 3, \tfrac32, \tfrac12, \tfrac13, \tfrac23, 2, 3, \dots. The pair (2,3)(2, 3) has reappeared as (a7,a8)(a_7, a_8), and each term depends on the previous two, so the period is 66.

Step 2. 2026=6⋅337+42026 = 6 \cdot 337 + 4, so a2026=a4=12a_{2026} = a_4 = \tfrac12.

Step 3. One full period multiplies to 2⋅3⋅32⋅12⋅13⋅23=12 \cdot 3 \cdot \tfrac32 \cdot \tfrac12 \cdot \tfrac13 \cdot \tfrac23 = 1. So the product of the first 20262026 terms is a1a2a3a4=2⋅3⋅32⋅12=92a_1a_2a_3a_4 = 2 \cdot 3 \cdot \tfrac32 \cdot \tfrac12 = \tfrac92.

Example
Worked: a recursion that hides a tangent
na48−3−2−112
The terms 2,−3,−1/2,1/32, -3, -1/2, 1/3 repeat every four steps.

a1=2a_1 = 2 and an+1=1+an1−ana_{n+1} = \dfrac{1 + a_n}{1 - a_n}. Find a100a_{100}.

Spotting it. The form 1+a1−a\tfrac{1 + a}{1 - a} is tan⁡(45∘+θ)\tan(45^\circ + \theta) when a=tan⁡θa = \tan\theta. Each step adds 45∘45^\circ to the angle, so four steps add 180∘180^\circ and the tangent repeats.

Step 1. Compute to confirm: a2=3−1=−3a_2 = \tfrac{3}{-1} = -3, a3=−24=−12a_3 = \tfrac{-2}{4} = -\tfrac12, a4=1/23/2=13a_4 = \tfrac{1/2}{3/2} = \tfrac13, a5=4/32/3=2a_5 = \tfrac{4/3}{2/3} = 2. Period 44.

Step 2. 100=4⋅25100 = 4 \cdot 25, so a100=a4=13a_{100} = a_4 = \tfrac13.

Side note
Where it goes wrong

Declaring a period from one repeated VALUE. For a recursion that uses the previous two terms, one repeat is not enough: an=an−1+an−2a_n = a_{n-1} + a_{n-2} mod 1010 starting 1,11, 1 shows the value 11 again at a8=21→1a_8 = 21 \to 1, but the sequence of last digits of Fibonacci numbers has period 6060, not 77. You need a whole window of consecutive terms to repeat.

Try it
Try it: a difference recursion

a1=1a_1 = 1, a2=2a_2 = 2 and an=an−1−an−2a_n = a_{n-1} - a_{n-2} for n≥3n \ge 3. Find a1+a2+⋯+a100a_1 + a_2 + \cdots + a_{100}.

Show the answer

The terms are 1,2,1,−1,−2,−1,1,2,…1, 2, 1, -1, -2, -1, 1, 2, \dots, with period 66 and sum 00 over each period. 100=6⋅16+4100 = 6 \cdot 16 + 4, so the sum is a1+a2+a3+a4=1+2+1−1=3a_1 + a_2 + a_3 + a_4 = 1 + 2 + 1 - 1 = 3.