What Comes Next, and Why

Draw a circle, then add chords (straight lines connecting two points on the circle) one at a time, always crossing all the earlier chords at new points. With 0 chords, the circle is 1 region. With 1 chord, 2 regions. With 2 chords, 4 regions. With 3 chords, 7 regions. With 4 chords, 11 regions. This growing list of numbers, 1, 2, 4, 7, 11, ..., is a sequence: an ordered list of numbers, where each number is called a term. Using tn to name the term in position n, this sequence has t1=1, t2=2, t3=4, t4=7, t5=11. The subscript n always matches the position, so t4=7 says the term in the 4th position is 7. Not every sequence has an obvious pattern in its rule at first glance, but every sequence, whatever its rule, can be talked about using this same tn notation.

Consider the sequence 5, 9, 13, 17, ... An explicit rule gives the nth term directly from n: here, tn = 4n+1, since t1=4(1)+1=5, t2=4(2)+1=9, and so on. A recursive rule instead builds each term from the one before: t1=5, tn=tn-1+4 for n greater than 1. Both rules describe the exact same sequence, but they answer different questions best. To check whether 205 is a term, the explicit rule is far quicker: solving 4n+1=205 gives 4n=204, so n=51, meaning 205 is indeed the 51st term. Checking whether 100 is a term: 4n+1=100 gives n=24.75, which is not a natural number, so 100 never appears in the sequence at all. An explicit rule turns 'is this number in the sequence' into a single equation to solve.

A bacterial colony starts with 10 bacteria, and every hour it triples in size, but then 5 bacteria die off from natural causes right after. This is described recursively: c1=10, cn=3cn-1-5 for n greater than 1. Computing forward: c2=3(10)-5=25, c3=3(25)-5=70, c4=3(70)-5=205, c5=3(205)-5=610, c6=3(610)-5=1825. Is 615 ever a term of this sequence? Unlike the previous explicit-rule example, there is no direct equation to solve here; the only way to check is to keep computing forward, term by term. Since the sequence jumps from 610 (the 5th term) to 1825 (the 6th term), and 615 falls in between without landing exactly on either, 615 is never a term. This is the real cost of a purely recursive rule: without an explicit formula, finding or checking a term means walking through every earlier term first.

A recursive rule does not have to depend on only the one term before it; it can depend on two or more earlier terms. The most famous such sequence is V1=1, V2=2, Vn=Vn-1+Vn-2 for n at least 3, giving V3=2+1=3, V4=3+2=5, V5=5+3=8, and so the sequence runs 1, 2, 3, 5, 8, 13, 21, 34, ..., each term the sum of the two before it. This is the Virahanka-Fibonacci sequence, first written down explicitly by the mathematician-poet Virahanka in the 7th century CE, in his work on the mathematics of Sanskrit and Prakrit poetic metre. It was studied further by Gopala around 1135 CE and Hemachandra around 1150 CE, and later, independently, by the Italian mathematician Fibonacci around 1200 CE. A different two-steps-back rule, with different starting values, describes an entirely different sequence: Q1=2, Q2=3, Q3=5, Qn=Qn-1+Qn-2+Qn-3 for n at least 4 (looking back THREE steps here) gives Q4=5+3+2=10, Q5=10+5+3=18, Q6=18+10+5=33, a sequence that grows following its own, equally valid, recursive rule.

An auditorium's first row has 24 seats, and each row behind it has 4 more seats than the row in front: 24, 28, 32, 36, ... Such a sequence, where the difference between consecutive terms is always the same constant, is called an Arithmetic Progression, or AP. Writing a for the first term and d for the common difference, an AP in general looks like a, a+d, a+2d, a+3d, ..., a+(n-1)d, giving the explicit rule tn = a+(n-1)d. Here a=24 and d=4, so tn = 24+(n-1)4 = 20+4n. The 18th row's seat count is t18 = 20+4(18) = 20+72 = 92 seats. Every AP also has a recursive rule, t1=a, tn=tn-1+d, but because the difference is constant, the explicit rule tn=a+(n-1)d is always available too, making an AP one of the few kinds of recursively-built sequences that also has a guaranteed direct formula.

Return to the chord-and-circle sequence from the start of this chapter, 1, 2, 4, 7, 11, ... Its differences are 1, 2, 3, 4, ..., an AP in their own right. To find how many regions n chords will make, first find the sum of the first (n-1) natural numbers and add 1. This calls for a formula for summing an AP of natural numbers 1, 2, 3, ..., n without adding term by term. Writing S = 1+2+...+12 and reversing it as S = 12+11+...+1, then adding the two, every pair (1+12, 2+11, and so on) sums to the same value, 13, and there are 12 such pairs, giving 2S = 13 x 12 = 156, so S = 78. In general, S = 1+2+...+n paired with its reverse gives every pair summing to (n+1), so 2S = n(n+1), meaning Sn = n(n+1)/2. Checking against the chord pattern: with 4 chords, the number of regions should be 1 + S3 = 1 + 3(4)/2 = 1+6 = 7, which matches exactly what was found by direct counting earlier.

Repeated folding of a strip of paper doubles its thickness each time. Starting at 0.1 mm thick, after each fold the thickness is 0.1, 0.2, 0.4, 0.8, ... millimetres: a sequence where every term is found by multiplying the previous one by a fixed number, here 2. Such a sequence is called a Geometric Progression, or GP, and in general looks like a, ar, ar^2, ar^3, ..., ar^(n-1), where a is the first term and r is the common ratio, giving the explicit rule tn = a x r^(n-1). Here tn = 0.1 x 2^(n-1), so after 10 folds the paper is t10 = 0.1 x 2^9 = 0.1 x 512 = 51.2 mm thick: a single strip, folded just 10 times, growing thicker than a stack of notebooks. A GP can also shrink: a court's case backlog of 4096 cases reduces to three-quarters of the previous year's backlog every year, thanks to a new clearing policy, giving 4096, 3072, 2304, ... with r = 3/4. After 4 years, the backlog is t4 = 4096 x (3/4)^3 = 4096 x 27/64 = 1728 cases. Growing or shrinking, both are the exact same kind of rule, a constant ratio, just with r greater than 1 or less than 1.