---
title: "Sequences: A First Course"
book: "High School Mathematics"
subject: math
language: en
chapter: 13
exercises: 11
source: https://one-course.com/books/math/2/en/chapter/13-sequences-a-first-course
---

# Chapter 13 — Sequences: A First Course

A [sequence](#def-g11-seq-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](#def-g11-seq-arithmetic)* [sequences](#def-g11-seq-sequence), which grow by equal steps, and *[geometric](#def-g11-seq-geometric)* [sequences](#def-g11-seq-sequence), which grow by equal ratios. The rigorous theory of limits is developed in [Chapter 20](https://one-course.com/books/math/2/en/chapter/20-sequences#ch-g12-seq).

## 13.1 Defining a sequence

**Definition 13.1 (Sequence).**

A *sequence* $(u_n)$ assigns to each [integer](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $n \geq 0$ (or $n \geq 1$) a [real number](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $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](#exo-g11-seq-11)).

## 13.2 Arithmetic sequences

**Definition 13.3 (Arithmetic sequence).**

A [sequence](#def-g11-seq-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](#def-g11-seq-arithmetic) with first term $u_0$ and [common difference](#def-g11-seq-arithmetic) $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](https://one-course.com/books/math/2/en/chapter/20-sequences#ch-g12-seq).) 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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $n \geq 1$:

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

More generally, a sum of consecutive terms of an [arithmetic sequence](#def-g11-seq-arithmetic) 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](#def-g11-seq-arithmetic) 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](#def-g11-seq-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](#def-g11-seq-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](#thm-g11-seq-arithgeneral): 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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $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.](https://one-course.com/images/onecourse/chapters/math-2/g11-seq/fig-7375b50ce909.svg)

*Equal steps versus equal ratios: an [arithmetic sequence](#def-g11-seq-arithmetic) ($u_{n+1} = u_n + 0.9$, blue) follows a line, a [geometric sequence](#def-g11-seq-geometric) ($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](#def-g11-seq-sequence) is [arithmetic](#def-g11-seq-arithmetic). Otherwise compute $\frac{u_{n+1}}{u_n}$ (terms nonzero) and simplify: a constant $q$ means [geometric](#def-g11-seq-geometric). If neither is constant, the [sequence](#def-g11-seq-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](#def-g11-seq-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](#def-g11-seq-arithmetic) nor [geometric](#def-g11-seq-geometric).

## 13.4 Monotonicity

**Definition 13.13 (Monotonic sequence).**

A [sequence](#def-g11-seq-sequence) $(u_n)$ is *[increasing](https://one-course.com/books/math/2/en/chapter/11-functions-and-variations#def-g11-func-monotone)* if $u_{n+1} \geq u_n$ for all $n$, and *[decreasing](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations)* 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](#def-g11-seq-sequence) with positive terms, one may instead compare $\frac{u_{n+1}}{u_n}$ to $1$.

**Example 13.15.**

An [arithmetic sequence](#def-g11-seq-arithmetic) is [increasing](https://one-course.com/books/math/2/en/chapter/11-functions-and-variations#def-g11-func-monotone) when $d \geq 0$ ($u_{n+1} - u_n = d$), [decreasing](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations) when $d \leq 0$. A [geometric sequence](#def-g11-seq-geometric) with $u_0 > 0$ and $q > 1$ is [increasing](https://one-course.com/books/math/2/en/chapter/11-functions-and-variations#def-g11-func-monotone): $u_{n+1} - u_n = u_0 q^n (q - 1) > 0$; with $u_0 > 0$ and $0 < q < 1$ it is [decreasing](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations).

## 13.5 Long-run behaviour, informally

What happens to $u_n$ when $n$ becomes very large? For an [arithmetic sequence](#def-g11-seq-arithmetic) with $d > 0$, the terms $u_0 + nd$ exceed any fixed number eventually. For a [geometric sequence](#def-g11-seq-geometric) 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](#ex-g11-seq-chessboard).

**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](https://one-course.com/books/math/2/en/chapter/20-sequences#ch-g12-seq).

## 13.6 Exercises

**Exercise 13.1 ★.**

For each [sequence](#def-g11-seq-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 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](#def-g11-seq-arithmetic) with $u_0 = 7$ and $d = -3$. Compute $u_{10}$ and $u_{25}$. $(v_n)$ is [arithmetic](#def-g11-seq-arithmetic) with $v_3 = 11$ and $v_8 = 26$. Find the [common difference](#def-g11-seq-arithmetic) and $v_0$.

**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](#def-g11-seq-geometric) with $u_0 = 5$ and $q = 2$. Compute $u_8$. $(v_n)$ is [geometric](#def-g11-seq-geometric) with positive terms, $v_2 = 12$ and $v_4 = 48$. Find the ratio and $v_0$.

**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 of Exercise 13.4.**

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

$4 + 7 + \dots + 61$ is [arithmetic](#def-g11-seq-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](#def-g11-seq-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](#def-g11-seq-sequence) is [arithmetic](#def-g11-seq-arithmetic), [geometric](#def-g11-seq-geometric), or neither:

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

**Solution of Exercise 13.5.**

$u_{n+1} - u_n = 4(n+1) - 1 - 4n + 1 = 4$: [arithmetic](#def-g11-seq-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](#def-g11-seq-geometric) with $q = \frac23$.

$w_0 = 0$, $w_1 = 2$, $w_2 = 6$: the differences $2$ and $4$ differ, so not [arithmetic](#def-g11-seq-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 of Exercise 13.6.**

The row sizes are [arithmetic](#def-g11-seq-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 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](#def-g11-seq-arithmetic) nor [geometric](#def-g11-seq-geometric).

**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](#def-g11-seq-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](#def-g11-seq-geometric). (Mixed “multiply then add” recursions like this one are solved by the [auxiliary-sequence](#def-g11-seq-sequence) trick of [Exercise 13.11](#exo-g11-seq-11).)

**Exercise 13.9 ★★.**

Study the monotonicity of the [sequences](#def-g11-seq-sequence)

$$
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 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](#def-g11-seq-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](#def-g11-seq-arithmetic) with $u_0 = 3$ and $d = 4$ equals $903$. Find $n$. (Set up a quadratic [equation](https://one-course.com/books/math/2/en/chapter/2-algebra-equations-and-inequalities#def-g10-algebra-equation) in $n$ and use [Chapter 10](https://one-course.com/books/math/2/en/chapter/10-quadratic-functions-and-equations#ch-g11-quad).)

**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](https://one-course.com/books/math/2/en/chapter/10-quadratic-functions-and-equations#def-g11-quad-discriminant) is rejected). Check: $21 \times 43 = 903$.

**Exercise 13.11 ★★★.**

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

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

**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](#def-g11-seq-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](https://one-course.com/books/math/2/en/chapter/3-functions#pb-g10-functions-1) of $x \mapsto 2x - 1$; the same idea reappears for $u_{n+1} = au_n + b$ in [Chapter 20](https://one-course.com/books/math/2/en/chapter/20-sequences#ch-g12-seq).)

## 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](#def-g11-seq-sequence) 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](#def-g11-seq-arithmetic), neither is [geometric](#def-g11-seq-geometric) — and both surrender to this chapter’s weapons: recurrences, [geometric](#def-g11-seq-geometric) sums ([Theorem 13.9](#thm-g11-seq-geomsum)), and the [auxiliary-sequence](#def-g11-seq-sequence) trick of [Exercise 13.11](#exo-g11-seq-11), which also computes your mortgage.

**Part I — The tower of Brahma.** The puzzle: $n$ disks of [decreasing](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations) 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.

1. Play (with coins) and record $h_1$ , $h_2$ , $h_3$ .
2. Explain the strategy behind the recurrence $h_{n+1} = 2h_n + 1$ : what must happen before and after the largest disk moves?
3. Solve the recurrence with the trick of [Exercise 13.11](#exo-g11-seq-11) : set $v_n = h_n + 1$ , show $(v_n)$ is [geometric](#def-g11-seq-geometric) , and conclude $h_n = 2^n - 1$ .
4. 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](#ex-g11-seq-chessboard) , the same giant in another story). Should we worry?
5. 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).

6. List $F_1$ through $F_{12}$ .
7. Show that $(F_n)$ is neither [arithmetic](#def-g11-seq-arithmetic) nor [geometric](#def-g11-seq-geometric) , but that it is strictly [increasing](https://one-course.com/books/math/2/en/chapter/11-functions-and-variations#def-g11-func-monotone) from $n = 2$ on ( [Method 13.14](#met-g11-seq-monotonicity) and the recurrence).
8. 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$.
9. 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.)
10. 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.
11. 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](#def-g11-seq-geometric) of ratio $\sqrt2$ .
12. 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](https://one-course.com/books/math/2/en/chapter/2-algebra-equations-and-inequalities#pb-g10-algebra-1) do the rabbits worship?

**Part III — The auxiliary trick, at the bank.**

13. Generalize [Exercise 13.11](#exo-g11-seq-11) : for $u_{n+1} = a\,u_n + b$ with $a \neq 1$ , let $\ell = \frac{b}{1 - a}$ (the [fixed point](https://one-course.com/books/math/2/en/chapter/3-functions#pb-g10-functions-1) ). Show $v_n = u_n - \ell$ is [geometric](#def-g11-seq-geometric) of ratio $a$ , and conclude $u_n = a^n (u_0 - \ell) + \ell$ .
14. 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](https://one-course.com/books/math/2/en/chapter/3-functions#pb-g10-functions-1) first!) to get an explicit formula for $d_n$ .
15. 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?
16. 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.**

17. Compute $1 + 2 + 3 + \dots + 1000$ ( [Theorem 13.5](#thm-g11-seq-intsum) — little Gauss’s sum from the Middle School volume, now official), and $1 + 2 + 4 + \dots + 2^{19}$ ( [Theorem 13.9](#thm-g11-seq-geomsum) ).
18. Compute the sum of the [arithmetic sequence](#def-g11-seq-arithmetic) $7, 12, 17, \dots, 502$ (how many terms?).
19. 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$ ).
20. Finale — the sequence-tamer’s kit: explicit against recurrent descriptions; the two royal families and their sum formulas; the auxiliary [sequence](#def-g11-seq-sequence) that turns affine recurrences into [geometric](#def-g11-seq-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 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](#def-g11-seq-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](#def-g11-seq-arithmetic) ($2 - 1 = 1$ but $3 - 2 = 1$, $5 - 3 = 2$: differences change); not [geometric](#def-g11-seq-geometric) ($\frac21 = 2$ but $\frac32 = 1.5$). [Increasing](https://one-course.com/books/math/2/en/chapter/11-functions-and-variations#def-g11-func-monotone): 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](#def-g11-seq-sequence) increases): every two indices, at least a doubling — growth at least [geometric](#def-g11-seq-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](https://one-course.com/books/math/2/en/chapter/2-algebra-equations-and-inequalities#pb-g10-algebra-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](#def-g11-seq-geometric) of ratio $a$. Hence $v_n = a^n v_0$ and $u_n = a^n (u_0 - \ell) + \ell$.

**14.** [Fixed point](https://one-course.com/books/math/2/en/chapter/3-functions#pb-g10-functions-1): $\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](https://one-course.com/books/math/2/en/chapter/3-functions#pb-g10-functions-1) $\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](#def-g11-seq-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](#def-g11-seq-arithmetic) add, [geometric](#def-g11-seq-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](#def-g11-seq-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.