High School Mathematics · Grades 10–12

13Sequences: A First Course

A sequence is a list of numbers produced by a rule: the successive balances of a savings account, the sizes of a population year after year. This chapter studies the two families that dominate applications — arithmetic sequences, which grow by equal steps, and geometric sequences, which grow by equal ratios. The rigorous theory of limits is developed in Chapter 20.

13.1 Defining a sequence

Definition 13.1 (Sequence)

A sequence $(u_n)$ assigns to each integer $n \geq 0$ (or $n \geq 1$ ) a real number $u_n$ , its term of index $n$ . A sequence can be given

explicitly, by a formula for $u_n$ in terms of $n$ : e.g. $u_n = n^2 + 1$ ;
recursively, by its first term and a rule to pass from each term to the next: e.g. $u_0 = 3$ and $u_{n+1} = 2u_n - 1$ .

Example 13.2

For $u_n = n^2 + 1$ : $u_0 = 1$ , $u_1 = 2$ , $u_2 = 5$ , and $u_{10} = 101$ directly. For $u_0 = 3$ , $u_{n+1} = 2u_n - 1$ : $u_1 = 5$ , $u_2 = 9$ , $u_3 = 17$ — each term needs the previous one; reaching $u_{10}$ takes ten steps (or a general formula, see Exercise 13.11).

13.2 Arithmetic sequences

Definition 13.3 (Arithmetic sequence)

A sequence is arithmetic with common difference $d$ if each term is obtained from the previous one by adding $d$ :

u_{n+1} = u_n + d \quad \text{for all } n.

Equivalently: the difference $u_{n+1} - u_n$ is constant, equal to $d$ .

Theorem 13.4 (General term)

If $(u_n)$ is arithmetic with first term $u_0$ and common difference $d$ , then

u_n = u_0 + n\,d \quad \text{for all } n \geq 0, \qquad\text{and more generally } u_n = u_p + (n - p)\,d .

Proof. To go from $u_0$ to $u_n$ , the rule “add $d$ ” is applied $n$ times: one step gives $u_1 = u_0 + d$ , two steps give $u_2 = u_0 + 2d$ , and after $n$ steps every application has contributed one $d$ , so $u_n = u_0 + nd$ . (This “and so on” is made rigorous by induction in Chapter 20.) The general formula follows by counting the $n - p$ steps from $u_p$ to $u_n$ . ∎

Theorem 13.5 (Sum of consecutive integers)

For every integer $n \geq 1$ :

1 + 2 + \dots + n = \frac{n(n+1)}{2}.

More generally, a sum of consecutive terms of an arithmetic sequence equals

(\text{number of terms}) \times \frac{\text{first term} + \text{last term}}{2}.

Proof. Write the sum $S$ twice, the second time in reverse order, and add column by column:

\begin{array}{ccccccccc} S & = & 1 & + & 2 & + & \dots & + & n\\ S & = & n & + & (n-1) & + & \dots & + & 1\\ \hline 2S & = & (n+1) & + & (n+1) & + & \dots & + & (n+1) \end{array}

There are $n$ columns, each summing to $n + 1$ , so $2S = n(n+1)$ . For a general arithmetic sequence the same pairing works: first $+$ last $=$ second $+$ second-to-last $= \dots$ , because moving one step forward at the left end ( $+d$ ) is compensated by one step backward at the right end ( $-d$ ). ∎

Example 13.6

$1 + 2 + \dots + 100 = \frac{100 \times 101}{2} = 5050$ . The sum of the odd numbers $1 + 3 + \dots + 99$ ( $50$ terms) is $50 \times \frac{1 + 99}{2} = 2500$ .

13.3 Geometric sequences

Definition 13.7 (Geometric sequence)

A sequence is geometric with common ratio $q \neq 0$ if each term is obtained from the previous one by multiplying by $q$ :

u_{n+1} = q\,u_n \quad \text{for all } n.

Equivalently, when no term vanishes: the ratio $\frac{u_{n+1}}{u_n}$ is constant, equal to $q$ .

Theorem 13.8 (General term)

If $(u_n)$ is geometric with first term $u_0$ and ratio $q$ , then

u_n = u_0\, q^n \quad \text{for all } n \geq 0, \qquad\text{and more generally } u_n = u_p\, q^{\,n-p} .

Proof. Same step-counting as in Theorem 13.4: from $u_0$ to $u_n$ , the rule “multiply by $q$ ” is applied $n$ times, contributing a factor $q^n$ . ∎

Theorem 13.9 (Geometric sum)

For every real $q \neq 1$ and integer $n \geq 0$ :

1 + q + q^2 + \dots + q^n = \frac{1 - q^{\,n+1}}{1 - q}.

Proof. Let $S = 1 + q + \dots + q^n$ . Multiply by $q$ : $qS = q + q^2 + \dots + q^{n+1}$ . Subtract:

S - qS = \bigl(1 + q + \dots + q^n\bigr) - \bigl(q + q^2 + \dots + q^{n+1}\bigr) = 1 - q^{\,n+1},

because every intermediate term appears once in each sum and cancels. Hence $(1 - q)S = 1 - q^{\,n+1}$ , and dividing by $1 - q \neq 0$ gives the formula. ∎

Example 13.10

$1 + 2 + 4 + \dots + 2^{10} = \frac{1 - 2^{11}}{1 - 2} = 2^{11} - 1 = 2047$ : doubling grains of rice on the squares of a chessboard overwhelms any granary well before the $64$ th square, where the total is $2^{64} - 1 \approx 1.8 \times 10^{19}$ .

Equal steps versus equal ratios: an arithmetic sequence (u_n+1 = u_n + 0.9, blue) follows a line, a geometric sequence (u_n+1 = 1.2\,u_n, red) follows an exponential curve that eventually outgrows it. — Equal steps versus equal ratios: an arithmetic sequence ( $u_{n+1} = u_n + 0.9$ , blue) follows a line, a geometric sequence ( $u_{n+1} = 1.2\,u_n$ , red) follows an exponential curve that eventually outgrows it.

Method 13.11 (Recognizing the type of a sequence)

Compute $u_{n+1} - u_n$ and simplify. If the result is a constant $d$ , the sequence is arithmetic. Otherwise compute $\frac{u_{n+1}}{u_n}$ (terms nonzero) and simplify: a constant $q$ means geometric. If neither is constant, the sequence is of neither type — never conclude from the first few terms alone.

Example 13.12

For $u_n = 3 \times 5^n$ : $\frac{u_{n+1}}{u_n} = \frac{3 \times 5^{n+1}}{3 \times 5^n} = 5$ for all $n$ : geometric with ratio $5$ . For $u_n = n^2$ : $u_1 - u_0 = 1$ but $u_2 - u_1 = 3$ , and $\frac{u_1}{u_0}$ is not even defined — neither arithmetic nor geometric.

13.4 Monotonicity

Definition 13.13 (Monotonic sequence)

A sequence $(u_n)$ is increasing if $u_{n+1} \geq u_n$ for all $n$ , and decreasing if $u_{n+1} \leq u_n$ for all $n$ .

Method 13.14 (Studying monotonicity)

Study the sign of $u_{n+1} - u_n$ . For sequences with positive terms, one may instead compare $\frac{u_{n+1}}{u_n}$ to $1$ .

Example 13.15

An arithmetic sequence is increasing when $d \geq 0$ ( $u_{n+1} - u_n = d$ ), decreasing when $d \leq 0$ . A geometric sequence with $u_0 > 0$ and $q > 1$ is increasing: $u_{n+1} - u_n = u_0 q^n (q - 1) > 0$ ; with $u_0 > 0$ and $0 < q < 1$ it is decreasing.

13.5 Long-run behaviour, informally

What happens to $u_n$ when $n$ becomes very large? For an arithmetic sequence with $d > 0$ , the terms $u_0 + nd$ exceed any fixed number eventually. For a geometric sequence with $0 < q < 1$ , the terms $u_0 q^n$ shrink towards $0$ : multiplying repeatedly by $0.9$ , say, erodes any starting value. And for $q > 1$ the terms explode, as in Example 13.10.

Remark 13.16

These statements can be made perfectly precise — “the terms eventually stay within any given distance of $0$ ” — and proved. That is the theory of limits, the opening theme of Chapter 20.

13.6 Exercises

Exercise 13.1 ★

For each sequence, compute $u_1$ , $u_2$ , $u_3$ :

u_n = \frac{n}{n+1}; \qquad u_0 = 5,\ u_{n+1} = 3u_n - 2; \qquad u_n = (-1)^n\,n .

Solution

Solution of Exercise 13.1.

$u_n = \frac{n}{n+1}$ : $u_1 = \frac12$ , $u_2 = \frac23$ , $u_3 = \frac34$ .

$u_0 = 5$ , $u_{n+1} = 3u_n - 2$ : $u_1 = 13$ , $u_2 = 37$ , $u_3 = 109$ .

$u_n = (-1)^n n$ : $u_1 = -1$ , $u_2 = 2$ , $u_3 = -3$ .

Exercise 13.2 ★

$(u_n)$ is arithmetic with $u_0 = 7$ and $d = -3$ . Compute $u_{10}$ and $u_{25}$ . $(v_n)$ is arithmetic with $v_3 = 11$ and $v_8 = 26$ . Find the common difference and $v_0$ .

Solution

Solution of Exercise 13.2.

$u_{10} = 7 + 10 \times (-3) = -23$ and $u_{25} = 7 - 75 = -68$ .

For $(v_n)$ : $v_8 = v_3 + 5d$ gives $26 = 11 + 5d$ , so $d = 3$ ; then $v_0 = v_3 - 3d = 11 - 9 = 2$ .

Exercise 13.3 ★

$(u_n)$ is geometric with $u_0 = 5$ and $q = 2$ . Compute $u_8$ . $(v_n)$ is geometric with positive terms, $v_2 = 12$ and $v_4 = 48$ . Find the ratio and $v_0$ .

Solution

Solution of Exercise 13.3.

$u_8 = 5 \times 2^8 = 1280$ .

For $(v_n)$ : $v_4 = v_2\, q^2$ gives $48 = 12 q^2$ , so $q^2 = 4$ and $q = 2$ (the terms are positive). Then $v_0 = \frac{v_2}{q^2} = \frac{12}{4} = 3$ .

Exercise 13.4 ★

Compute

1 + 2 + 3 + \dots + 500, \qquad 4 + 7 + 10 + \dots + 61, \qquad 1 + \frac12 + \frac14 + \dots + \frac{1}{2^{10}} .

Solution

Solution of Exercise 13.4.

$1 + \dots + 500 = \frac{500 \times 501}{2} = 125\,250$ .

$4 + 7 + \dots + 61$ is arithmetic with $d = 3$ and $\frac{61 - 4}{3} + 1 = 20$ terms: sum $20 \times \frac{4 + 61}{2} = 650$ .

$1 + \frac12 + \dots + \frac{1}{2^{10}}$ is geometric with $q = \frac12$ and $11$ terms: $\frac{1 - (1/2)^{11}}{1 - 1/2} = 2\left(1 - \frac{1}{2048}\right) = \frac{2047}{1024}$ .

Exercise 13.5 ★

Determine whether each sequence is arithmetic, geometric, or neither:

u_n = 4n - 1; \qquad v_n = \frac{2^n}{3^{n+1}}; \qquad w_n = n^2 + n .

Solution

Solution of Exercise 13.5.

$u_{n+1} - u_n = 4(n+1) - 1 - 4n + 1 = 4$ : arithmetic with $d = 4$ .

$\frac{v_{n+1}}{v_n} = \frac{2^{n+1}}{3^{n+2}} \cdot \frac{3^{n+1}}{2^n} = \frac23$ : geometric with $q = \frac23$ .

$w_0 = 0$ , $w_1 = 2$ , $w_2 = 6$ : the differences $2$ and $4$ differ, so not arithmetic; $\frac{w_1}{w_0}$ is not even defined, and the ratios $\frac{w_2}{w_1} = 3 \neq \frac{w_3}{w_2} = 2$ : neither.

Exercise 13.6 ★★

A theater has $20$ rows: $16$ seats in the first row, and each row has $2$ more seats than the one before it. How many seats are in the last row? In the whole theater?

Solution

Solution of Exercise 13.6.

The row sizes are arithmetic: first term $16$ , difference $2$ . The last (20th) row has $16 + 19 \times 2 = 54$ seats. The total is $20 \times \frac{16 + 54}{2} = 700$ seats.

Exercise 13.7 ★★

A population of bacteria doubles every hour; at noon there are $500$ bacteria. How many are there at 8 p.m.? After how many full hours does the population first exceed one million? (Solve by trying successive powers of $2$ .)

Solution

Solution of Exercise 13.7.

After $n$ hours the population is $500 \times 2^n$ . At 8 p.m., $n = 8$ : $500 \times 256 = 128\,000$ bacteria. We need $500 \times 2^n > 10^6$ , i.e. $2^n > 2000$ : since $2^{10} = 1024$ and $2^{11} = 2048$ , the population first exceeds one million after $11$ full hours, at 11 p.m.

Exercise 13.8 ★★

Every month, a saver deposits $100$ euros into an account that pays $0.2\%$ interest per month on the existing balance (interest is credited just before the deposit). Let $c_n$ be the balance right after the $n$ -th deposit, so $c_1 = 100$ and $c_{n+1} = 1.002\,c_n + 100$ . Compute $c_2$ and $c_3$ , and explain why $(c_n)$ is neither arithmetic nor geometric.

Solution

Solution of Exercise 13.8.

$c_2 = 1.002 \times 100 + 100 = 200.20$ and $c_3 = 1.002 \times 200.20 + 100 \approx 300.60$ . The differences $c_2 - c_1 = 100.20$ and $c_3 - c_2 \approx 100.40$ are not equal, so $(c_n)$ is not arithmetic; the ratios $\frac{c_2}{c_1} = 2.002$ and $\frac{c_3}{c_2} \approx 1.50$ are not equal either, so it is not geometric. (Mixed “multiply then add” recursions like this one are solved by the auxiliary-sequence trick of Exercise 13.11.)

Exercise 13.9 ★★

Study the monotonicity of the sequences

u_n = n^2 - 8n \ (n \geq 0), \qquad v_n = \frac{3^n}{n!}\ (n \geq 1),

where $n! = 1 \times 2 \times \dots \times n$ . (For $(v_n)$ , compare $\frac{v_{n+1}}{v_n}$ to $1$ .)

Solution

Solution of Exercise 13.9.

$u_{n+1} - u_n = (n+1)^2 - 8(n+1) - n^2 + 8n = 2n - 7$ : negative for $n \leq 3$ , positive for $n \geq 4$ . So $(u_n)$ decreases down to $u_4 = 16 - 32 = -16$ , then increases: it is not monotonic.

$(v_n)$ has positive terms and

\frac{v_{n+1}}{v_n} = \frac{3^{n+1}}{(n+1)!} \cdot \frac{n!}{3^n} = \frac{3}{n+1},

which is $> 1$ for $n \leq 1$ , $= 1$ for $n = 2$ , and $< 1$ for $n \geq 3$ : the sequence increases up to $v_2 = v_3 = \frac92$ , then decreases.

Exercise 13.10 ★★

The sum of the first $n$ terms of an arithmetic sequence with $u_0 = 3$ and $d = 4$ equals $903$ . Find $n$ . (Set up a quadratic equation in $n$ and use Chapter 10.)

Solution

Solution of Exercise 13.10.

The first $n$ terms are $u_0, \dots, u_{n-1}$ , with $u_0 = 3$ and $u_{n-1} = 3 + 4(n-1) = 4n - 1$ . Their sum is

n \times \frac{3 + (4n-1)}{2} = n(2n + 1) = 903,

so $2n^2 + n - 903 = 0$ . Here $\Delta = 1 + 4 \times 2 \times 903 = 7225 = 85^2$ , and $n = \frac{-1 + 85}{4} = 21$ (the negative root is rejected). Check: $21 \times 43 = 903$ .

Exercise 13.11 ★★★

Let $u_0 = 3$ and $u_{n+1} = 2u_n - 1$ .

Compute $u_1, u_2, u_3$ and conjecture a formula for $u_n$ .
Let $v_n = u_n - 1$ . Show that $(v_n)$ is geometric, give its ratio and first term.
Deduce an explicit formula for $u_n$ and verify your conjecture.

Solution

Solution of Exercise 13.11.

1. $u_1 = 5$ , $u_2 = 9$ , $u_3 = 17$ : each term is one more than $4, 8, 16$ , suggesting $u_n = 2^{n+1} + 1$ .

2. With $v_n = u_n - 1$ :

v_{n+1} = u_{n+1} - 1 = 2u_n - 1 - 1 = 2(u_n - 1) = 2v_n,

so $(v_n)$ is geometric with ratio $2$ and first term $v_0 = u_0 - 1 = 2$ .

3. Hence $v_n = 2 \times 2^n = 2^{n+1}$ and $u_n = v_n + 1 = 2^{n+1} + 1$ , confirming the conjecture. (The number $1$ subtracted in $v_n$ is the fixed point of $x \mapsto 2x - 1$ ; the same idea reappears for $u_{n+1} = au_n + b$ in Chapter 20.)

13.7 Problem: The tower of Brahma and Fibonacci’s rabbits

Problem 13.1

Weekend problem — two legendary recurrences: the tower that ends the world, the sequence that grows like gold, and the auxiliary trick that tames loans

Two sequences rule the folklore of mathematics. One counts the moves of the tower of Brahma — sixty-four golden disks whose transfer, legend says, will end the world. The other counts Fibonacci’s rabbits and hides the golden ratio. Neither is arithmetic, neither is geometric — and both surrender to this chapter’s weapons: recurrences, geometric sums (Theorem 13.9), and the auxiliary-sequence trick of Exercise 13.11, which also computes your mortgage.

Part I — The tower of Brahma. The puzzle: $n$ disks of decreasing size are stacked on peg A; move the whole stack to peg C, one disk at a time, never placing a larger disk on a smaller one (peg B may help). Let $h_n$ be the minimal number of moves.

Play (with coins) and record $h_1$ , $h_2$ , $h_3$ .
Explain the strategy behind the recurrence $h_{n+1} = 2h_n + 1$ : what must happen before and after the largest disk moves?
Solve the recurrence with the trick of Exercise 13.11: set $v_n = h_n + 1$ , show $(v_n)$ is geometric, and conclude $h_n = 2^n - 1$ .
The legend’s tower has $64$ disks, and the monks move one disk per second. Using $2^{10} = 1024 \approx 10^3$ , estimate the transfer time in years (a year is about $3 \times 10^7$ seconds; compare Example 13.10, the same giant in another story). Should we worry?
Why can no strategy beat $2^n - 1$ moves? Argue that any solution obeys $h_{n+1} \geq 2 h_n + 1$ : what must be true of the top $n$ disks just before, and just after, the bottom disk’s move?

Part II — Fibonacci. Define $F_1 = F_2 = 1$ and $F_{n+2} = F_{n+1} + F_n$ (each term the sum of the two before — the rhythm-counting rule of the Middle School volume, now with its European name).

List $F_1$ through $F_{12}$ .
Show that $(F_n)$ is neither arithmetic nor geometric, but that it is strictly increasing from $n = 2$ on (Method 13.14 and the recurrence).
Prove the sum identity

$F_1 + F_2 + \dots + F_n = F_{n+2} - 1$

by telescoping: write each $F_k$ as $F_{k+2} - F_{k+1}$ and watch the sum collapse. Verify it for $n = 6$ .
Prove the squares identity $F_1^2 + F_2^2 + \dots + F_n^2 = F_n F_{n+1}$ , telescoping with $F_k F_{k+1} - F_{k-1} F_k = F_k^2$ . Verify for $n = 4$ . (Picture: squares of sides $1, 1, 2, 3, 5, \dots$ tile a rectangle — the famous Fibonacci spiral’s skeleton.)
Cassini’s identity states $F_{n+1} F_{n-1} - F_n^2 = (-1)^n$ . Verify it for $n = 4, 5, 6$ — and recognize the engine of the vanishing-square trick played in the Middle School volume’s areas problem.
Show from the recurrence that $F_{n+2} \geq 2 F_n$ : Fibonacci at least doubles every two steps — it grows at least as fast as a geometric sequence of ratio $\sqrt2$ .
Compute the ratios $r_n = \frac{F_{n+1}}{F_n}$ for $n = 3$ to $10$ (three decimals). Admitting that they settle on a limit $L$ , pass the relation $r_{n+1} = 1 + \frac{1}{r_n}$ to the limit and solve: which number of Problem 2.1 do the rabbits worship?

Part III — The auxiliary trick, at the bank.

Generalize Exercise 13.11: for $u_{n+1} = a\,u_n + b$ with $a \neq 1$ , let $\ell = \frac{b}{1 - a}$ (the fixed point). Show $v_n = u_n - \ell$ is geometric of ratio $a$ , and conclude $u_n = a^n (u_0 - \ell) + \ell$ .
A loan: $10\,000$ euros at $1\,\%$ interest per month, repaid $300$ euros per month, so the debt obeys $d_{n+1} = 1.01\,d_n - 300$ . Apply question 13 (fixed point first!) to get an explicit formula for $d_n$ .
With a calculator, find the first month at which the debt is cleared, and the total amount repaid. How much did the borrowing itself cost?
A town of $50\,000$ inhabitants grows by $2\,\%$ a year and welcomes $1\,000$ newcomers besides: $p_{n+1} = 1.02\,p_n + 1000$ . Give the explicit formula and the population after $10$ years.

Part IV — The two royal families.

Compute $1 + 2 + 3 + \dots + 1000$ (Theorem 13.5 — little Gauss’s sum from the Middle School volume, now official), and $1 + 2 + 4 + \dots + 2^{19}$ (Theorem 13.9).
Compute the sum of the arithmetic sequence $7, 12, 17, \dots, 502$ (how many terms?).
Savings plan: $100$ euros deposited each month, earning $0.5\,\%$ monthly; after the $n$ -th deposit the balance is $100\left(1.005^{n-1} + \dots + 1.005 + 1\right)$ . Compute the balance after $5$ years ( $n = 60$ ).
Finale — the sequence-tamer’s kit: explicit against recurrent descriptions; the two royal families and their sum formulas; the auxiliary sequence that turns affine recurrences into geometric ones; and Fibonacci, first citizen outside both families, tamed today by identities and awaiting matrices (grade 12) and limits for full capture. One sentence each.

Solution

Solution of Problem 13.1.

1. $h_1 = 1$ , $h_2 = 3$ , $h_3 = 7$ .

2. To move the biggest disk, the $n$ disks above it must first migrate to the spare peg ( $h_n$ moves); the big disk crosses ( $1$ move); the $n$ disks must then climb back on top of it ( $h_n$ moves): $h_{n+1} = 2h_n + 1$ .

3. $v_{n+1} = h_{n+1} + 1 = 2h_n + 2 = 2v_n$ : geometric of ratio $2$ with $v_1 = 2$ , so $v_n = 2^n$ and $h_n = 2^n - 1$ .

4. $2^{64} - 1 \approx 1.8 \times 10^{19}$ seconds; dividing by $3 \times 10^7$ seconds per year: about $6 \times 10^{11}$ years — six hundred billion years, forty times the age of the universe. The monks can take coffee breaks.

5. In any legal solution, consider the bottom disk’s first move: at that instant the other $n$ disks must all sit on the one remaining peg (at least $h_n$ moves to get them there), and after the bottom disk’s last move they must all come back on top of it (at least $h_n$ more): any solution needs at least $2h_n + 1$ moves. The recurrence is a floor as well as a ceiling: $2^n - 1$ is optimal.

6. $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144$ .

7. Not arithmetic ( $2 - 1 = 1$ but $3 - 2 = 1$ , $5 - 3 = 2$ : differences change); not geometric ( $\frac21 = 2$ but $\frac32 = 1.5$ ). Increasing: for $n \geq 2$ , $F_{n+1} - F_n = F_{n-1} > 0$ .

8. $F_k = F_{k+2} - F_{k+1}$ , so

\sum_{k=1}^{n} F_k = (F_3 - F_2) + (F_4 - F_3) + \dots + (F_{n+2} - F_{n+1}) = F_{n+2} - F_2 = F_{n+2} - 1 .

For $n = 6$ : $1 + 1 + 2 + 3 + 5 + 8 = 20 = F_8 - 1 = 21 - 1$ .

9. $F_k F_{k+1} - F_{k-1} F_k = F_k (F_{k+1} - F_{k-1}) = F_k \cdot F_k = F_k^2$ ; summing telescopes to $F_n F_{n+1} - F_1 F_0$ (with $F_0 = 0$ ): the sum of squares is $F_n F_{n+1}$ . For $n = 4$ : $1 + 1 + 4 + 9 = 15 = F_4 F_5 = 3 \times 5$ .

10. $F_5 F_3 - F_4^2 = 5 \times 2 - 9 = 1$ ; $F_6 F_4 - F_5^2 = 8 \times 3 - 25 = -1$ ; $F_7 F_5 - F_6^2 = 13 \times 5 - 64 = 1$ : alternating $\pm 1$ . This off-by-one between $F_{n+1} F_{n-1}$ and $F_n^2$ is exactly the magician’s gained-or-lost square unit: cutting a $F_n \times F_n$ square into pieces reassembled as an $F_{n+1} \times F_{n-1}$ rectangle must create or swallow one unit — the sliver.

11. $F_{n+2} = F_{n+1} + F_n \geq F_n + F_n = 2F_n$ (the sequence increases): every two indices, at least a doubling — growth at least geometric of ratio $\sqrt2$ per index.

12. $1.5$ ; $1.667$ ; $1.6$ ; $1.625$ ; $1.615$ ; $1.619$ ; $1.618$ ; $1.618$ . If $r_n \to L$ : from $F_{n+2} = F_{n+1} + F_n$ , dividing by $F_{n+1}$ : $r_{n+1} = 1 + \frac{1}{r_n}$ , so $L = 1 + \frac1L$ , i.e. $L^2 = L + 1$ : $L = \varphi = \frac{1 + \sqrt5}{2}$ , the golden ratio of Problem 2.1. The rabbits multiply in gold.

13. $v_{n+1} = u_{n+1} - \ell = a u_n + b - \ell$ ; since $\ell = a\ell + b$ , this is $a(u_n - \ell) = a v_n$ : geometric of ratio $a$ . Hence $v_n = a^n v_0$ and $u_n = a^n (u_0 - \ell) + \ell$ .

14. Fixed point: $\ell = 1.01\ell - 300$ gives $\ell = 30\,000$ . So $d_n = 1.01^n (10\,000 - 30\,000) + 30\,000 = 30\,000 - 20\,000 \times 1.01^n$ .

15. $d_n \leq 0$ requires $1.01^n \geq 1.5$ : $1.01^{40} \approx 1.489$ , $1.01^{41} \approx 1.504$ : the $41$ st payment clears the debt (and is slightly smaller than $300$ ). Total repaid: just under $41 \times 300 = 12\,300$ euros — the $10\,000$ borrowed cost about $2\,300$ euros of interest.

16. Fixed point $\ell = \frac{1000}{1 - 1.02} = -50\,000$ , so $p_n = 1.02^n \times 100\,000 - 50\,000$ . After $10$ years: $1.02^{10} \approx 1.219$ : $p_{10} \approx 71\,900$ inhabitants.

17. $\frac{1000 \times 1001}{2} = 500\,500$ ; and $2^{20} - 1 = 1\,048\,575$ .

18. From $7$ to $502$ in steps of $5$ : $\frac{502 - 7}{5} + 1 = 100$ terms; sum $= 100 \times \frac{7 + 502}{2} = 25\,450$ .

19. Balance $= 100 \times \frac{1.005^{60} - 1} {1.005 - 1} \approx 100 \times \frac{0.3489}{0.005} \approx 6\,977$ euros — of which $6\,000$ deposited and about $977$ earned: geometric sums are the bank’s native tongue.

20. Explicit formulas answer “what is $u_{1000}$ ” instantly; recurrences describe how systems actually evolve — the art is converting the second into the first. Arithmetic sequences add, geometric ones multiply, and each family owns a sum formula (Gauss’s pairing; the doubling trick). The fixed-point-and-auxiliary trick converts every affine recurrence into a geometric one — loans, populations, and the tower all fell to it. Fibonacci obeys neither family, yet telescoping identities caught its sums and squares; its full portrait (an exact formula, the golden limit) awaits stronger tools.