← MA0 2 · Introduction to Algorithms and Numerical Analysis

Lesson 2

Recurrences and Sums

Taught 26 Aug 2026

Recurrences

A recurrence defines a quantity at one value of $n$ in terms of its values at smaller ones, together with enough starting values to get the definition off the ground. Counting problems produce recurrences readily, because the natural way to attack a problem of size $n$ is often to remove one piece and be left with a problem of the same kind and smaller size. What a recurrence does not do is answer a question quickly: getting at the millionth term by following the definition means computing the first million, and the work of this chapter is to replace such a definition by a formula that can be evaluated in one step.

The Tower of Hanoi

Édouard Lucas put the following puzzle on sale in 1883. Three pegs stand in a row, and on the first of them sit $n$ discs of distinct sizes, stacked largest at the bottom and smallest on top. A move lifts the top disc off one peg and drops it onto another, and it is illegal to place a disc on top of a smaller one. The object is to move the whole stack onto a different peg.

Figure 2.1. The Tower of Hanoi with four discs. No disc may ever rest on a smaller one.

Write $T_n$ for the least number of legal moves that carries a stack of $n$ discs from one peg to another. With one disc a single move does it, so $T_1 = 1$ . With two, the small disc goes to the spare peg, the large one to the target, and the small one on top of it: $T_2 = 3$ . With three the shortest solution takes seven moves,

\begin{aligned} &d_1 \to C, \quad d_2 \to B, \quad d_1 \to B, \quad d_3 \to C, \\ &d_1 \to A, \quad d_2 \to C, \quad d_1 \to C, \end{aligned}

and with four it takes fifteen. The counts so far run $1, 3, 7, 15, 31, 63$ .

Proposition 2.1 (The Hanoi recurrence).

For every $n \in \mathbb{N}$ ,

T_n = 2T_{n-1} + 1,

and $T_0 = 0$ .

Discussion.

An equality between two counts is two inequalities, and each is argued differently. For $T_n \leqslant 2T_{n-1} + 1$ we exhibit a strategy costing that many moves and appeal to $T_n$ being the least cost: shift the top $n-1$ discs to the spare peg, move the largest, shift the $n-1$ back on top of it. The two shifts are legal because the largest disc is out of the way in the first and sits below everything in the second, so neither is obstructed. For $T_n \geqslant 2T_{n-1} + 1$ we argue about an arbitrary solution rather than a chosen one, and the pivot is the largest disc: it has to move at some point, and at the first moment it moves, the other $n-1$ discs are on one peg and not on either of the two the largest disc occupies, since none of them may sit on top of it or under it in the destination. Reaching that position costs at least $T_{n-1}$ , the move itself costs one, and rebuilding the stack afterwards costs at least $T_{n-1}$ again.

Proof.

There are no discs to move when $n = 0$ , so $T_0 = 0$ .

Let $n \in \mathbb{N}$ . For the upper bound, carry out the following. Move the top $n-1$ discs from the source peg to the spare peg, which is possible in $T_{n-1}$ moves and remains legal with the largest disc left in place, since that disc is larger than all of them and lies at the bottom of the source peg. Move the largest disc to the target peg: one move. Move the $n-1$ discs from the spare peg onto the target peg, again $T_{n-1}$ moves, legal because they all land on the largest disc. That is $2T_{n-1} + 1$ moves in all, so $T_n \leqslant 2T_{n-1} + 1$ .

For the lower bound, take any legal sequence of moves carrying the stack from the source to the target. The largest disc must move at least once. Consider the first move that lifts it. Just before that move the other $n-1$ discs lie neither on the peg it leaves nor on the peg it arrives at: not the first, because they are all smaller and would have to be above it; not the second, because it may not land on a smaller disc. So all $n-1$ of them are stacked on the remaining peg, and getting them there from the source peg took at least $T_{n-1}$ moves. After the largest disc has reached the target for the last time, the $n-1$ discs must be brought from that third peg onto it, which takes at least $T_{n-1}$ moves more, and the moves of the largest disc themselves account for at least one. Hence $T_n \geqslant 2T_{n-1} + 1$ .

Closed Forms

Computing $T_{100}$ from the recurrence means computing $T_1$ through $T_{99}$ first. What we want instead is a function $f$ with $f(n) = T_n$ for every $n$ , evaluable on its own. The sequence $0, 1, 3, 7, 15, 31, 63$ sits one below the powers of two, which is enough to make a guess.

Proposition 2.2 (Closed form for the Tower of Hanoi).

For every $n \in \mathbb{N}_0$ we have $T_n = 2^n - 1$ .

Discussion.

The recurrence defines $T_n$ from $T_{n-1}$ , so a claim about all $n$ is proved by induction, and the induction has exactly the shape of the recurrence: one base case at $n = 0$ , and a step that rewrites $T_n$ as $2T_{n-1} + 1$ , replaces $T_{n-1}$ by the inductive hypothesis, and simplifies. Nothing has to be discovered during the proof; the formula was guessed from the first few terms, and induction only certifies it.

Proof.

For $n = 0$ we have $T_0 = 0$ and $2^0 - 1 = 0$ .

Suppose $T_{n-1} = 2^{n-1} - 1$ for some $n \in \mathbb{N}$ . By the recurrence,

T_n = 2T_{n-1} + 1 = 2\bigl(2^{n-1} - 1\bigr) + 1 = 2^n - 2 + 1 = 2^n - 1,

which is the claim at $n$ .

Induction certifies a formula but does not produce one, and guessing from a handful of terms is not a method. Two techniques that do produce the formula follow.

Unrolling. Apply the recurrence to itself repeatedly and watch what accumulates:

\begin{aligned} T_n &= 2T_{n-1} + 1 \\ &= 2\bigl(2T_{n-2} + 1\bigr) + 1 = 4T_{n-2} + 2 + 1 \\ &= 4\bigl(2T_{n-3} + 1\bigr) + 2 + 1 = 8T_{n-3} + 4 + 2 + 1 . \end{aligned}

The pattern is

T_n = 2^k T_{n-k} + 2^{k-1} + 2^{k-2} + \cdots + 2 + 1 = 2^k T_{n-k} + 2^k - 1,

and one more application confirms that it reproduces itself:

2^k T_{n-k} + 2^k - 1 = 2^k\bigl(2T_{n-k-1} + 1\bigr) + 2^k - 1 = 2^{k+1}T_{n-k-1} + 2^{k+1} - 1,

which is the same expression with $k+1$ in place of $k$ . Since the case $k = 1$ is the recurrence itself, the displayed identity holds for every $k$ with $1 \leqslant k \leqslant n$ by induction on $k$ . Taking $k = n$ leaves $T_n$ in terms of a value we know,

T_n = 2^n T_0 + 2^n - 1 = 2^n - 1 .

Remark (The geometric sum).

The step from $2^{k-1} + \cdots + 2 + 1$ to $2^k - 1$ is worth doing once. Writing $S = 2^{k-1} + \cdots + 2 + 1$ and doubling gives $2S = 2^k + 2^{k-1} + \cdots + 2$ , so $2S - S = 2^k - 1$ , that is $S = 2^k - 1$ . The same trick evaluates $1 + q + \cdots + q^{k-1}$ as $(q^k - 1)/(q - 1)$ for any $q \neq 1$ .

Substitution. Rather than solve the recurrence, change the unknown so that the recurrence becomes one we can already solve. Adding $1$ to both sides of $T_n = 2T_{n-1} + 1$ gives

T_n + 1 = 2T_{n-1} + 2 = 2\bigl(T_{n-1} + 1\bigr),

so if we set $U_n = T_n + 1$ then $U_0 = 1$ and $U_n = 2U_{n-1}$ for $n \geqslant 1$ . That recurrence doubles at every step, so $U_n = 2^n$ , and therefore $T_n = U_n - 1 = 2^n - 1$ .

Problem 2.1.

Show that in the strategy of the proof of the Hanoi recurrence every disc moves at least once, and that the smallest disc moves on every second move.

Problem 2.2.

Suppose the three pegs are arranged in a row and a disc may only be moved between adjacent pegs, so that a move from the left peg to the right peg is forbidden. Let $S_n$ be the least number of moves needed to transfer a stack of $n$ discs from the left peg to the right peg. Find a recurrence for $S_n$ and solve it.

Lines in the Plane

Here is a second problem of the same shape. What is the largest number $L_n$ of regions into which $n$ straight lines can cut the plane?

With no lines there is one region, so $L_0 = 1$ . One line cuts the plane in two however it is drawn, so $L_1 = 2$ . Two lines do best when they are not parallel, giving $L_2 = 4$ . At this point $1, 2, 4$ invites the guess $L_n = 2^n$ , and the guess fails at once: a third line meets the two existing ones in at most two points, which divide it into at most three pieces, and each piece splits one old region in two. So the third line adds at most three regions and $L_3 = 7$ , not $8$ .

Figure 2.2. Three lines, no two parallel and no three through a common point, cut the plane into seven regions.

Proposition 2.3 (The line recurrence).

For every $n \in \mathbb{N}$ ,

L_n = L_{n-1} + n,

and $L_0 = 1$ .

Discussion.

Again the equality splits into two inequalities about the $n$ th line added to $n-1$ already drawn. For the upper bound, the new line gains exactly as many regions as the number of old regions it passes through, and it passes through one more region than the number of points at which it meets the old lines. Two distinct lines meet in at most one point, so the new line meets $n-1$ old lines in at most $n-1$ points and gains at most $n$ regions. For the lower bound we must place the new line so that both estimates are attained: not parallel to any old line, which forces it to meet each of them, and not through any existing intersection point, which keeps the $n-1$ meeting points distinct. Only finitely many directions and finitely many points have to be avoided, so such a line exists.

Proof.

With no lines drawn the plane is a single region, so $L_0 = 1$ .

Let $n \in \mathbb{N}$ and suppose $n-1$ lines have been drawn. Adding a line $\ell$ increases the number of regions by exactly the number of old regions that $\ell$ passes through, since each such region is cut into two and no other region is touched. The old lines meet $\ell$ in some set of points, and those points cut $\ell$ into one more piece than there are points, with each piece lying in one old region. Two distinct lines meet in at most one point, so $\ell$ meets the $n-1$ old lines in at most $n-1$ points and therefore passes through at most $n$ old regions. Hence $L_n \leqslant L_{n-1} + n$ .

For the reverse, take $n-1$ lines realising $L_{n-1}$ regions. The old lines have $n-1$ directions and finitely many pairwise intersection points, so we may choose $\ell$ parallel to none of them and passing through none of those points. Then $\ell$ meets every old line, in $n-1$ distinct points, so it passes through exactly $n$ old regions and adds $n$ new ones. Hence $L_n \geqslant L_{n-1} + n$ .

Unrolling this recurrence gives

\begin{aligned} L_n &= L_{n-1} + n = L_{n-2} + (n-1) + n = L_{n-3} + (n-2) + (n-1) + n \\ &= L_0 + 1 + 2 + \cdots + n = 1 + \frac{n(n+1)}{2}, \end{aligned}

using the sum of the first $n$ positive integers.

Problem 2.3.

Prove by induction that $L_n = 1 + \tfrac{1}{2}n(n+1)$ for every $n \in \mathbb{N}_0$ .

Problem 2.4.

Prove that $1 + 2 + \cdots + n = \tfrac{1}{2}n(n+1)$ for every $n \in \mathbb{N}_0$ , by pairing the first term with the last, the second with the second-last, and so on.

Problem 2.5.

What is the largest number of regions into which $n$ lines can cut the plane if all $n$ lines are required to pass through a common point?

Problem 2.6.

A zig is a bent line, made of two rays issuing from a common point. Find and solve a recurrence for the largest number of regions into which $n$ zigs can cut the plane.

Linear Recurrences

Guessing and unrolling both depend on the recurrence being simple enough to see through. A large family of recurrences can be solved by a recipe that needs no insight at all, and this section develops it.

How many ways are there to climb a staircase of $n$ steps, if each stride goes up either one step or two? For four steps there are five ways:

\begin{aligned} &1,1,1,1 \qquad 2,2 \qquad 2,1,1 \\ &1,2,1 \qquad 1,1,2 \end{aligned}

There is one way to climb no steps, namely to do nothing, and one way to climb one step. For $n \geqslant 2$ any ascent begins with either a stride of one, leaving an ascent of $n-1$ steps, or a stride of two, leaving an ascent of $n-2$ ; the two cases are exclusive and exhaust the possibilities. Writing $f(n)$ for the number of ascents of $n$ steps,

f(0) = 1, \qquad f(1) = 1, \qquad f(n) = f(n-1) + f(n-2) \quad (n \geqslant 2).

This is the Fibonacci recurrence, introduced in 1202 to model rabbit populations and unsolved in closed form for nearly six centuries. We use $f(n)$ rather than $f_n$ from here on, since the argument will shortly be something other than an integer.

Definition 2.4 (Linear recurrence).

A homogeneous linear recurrence of order $d$ is one of the form

f(n) = a_1 f(n-1) + a_2 f(n-2) + \cdots + a_d f(n-d),

where $a_1, \ldots, a_d$ are constants with $a_d \neq 0$ . Values of $f$ prescribed at finitely many points are its boundary conditions. Adding a further term $g(n)$ on the right, where $g$ is a fixed function, gives an inhomogeneous linear recurrence.

The Fibonacci recurrence has order $2$ with $a_1 = a_2 = 1$ , and the boundary conditions $f(0) = f(1) = 1$ .

Theorem 2.5 (Solutions form a linear space).

Let $f$ and $g$ both satisfy the homogeneous linear recurrence with coefficients $a_1, \ldots, a_d$ . Then for all $s, t \in \mathbb{R}$ the function $h(n) = s f(n) + t g(n)$ satisfies it too.

Discussion.

The recurrence is an identity that must hold at every $n$ , so the proof evaluates the right-hand side of the recurrence at $h$ and pushes it back to $h(n)$ . Two facts do all the work, and both are about arithmetic rather than about recurrences: the right-hand side is a sum of terms each of which is a constant times a value of the function, so it distributes over the combination $sf + tg$ ; and the hypotheses on $f$ and $g$ let each of the two resulting sums collapse to $f(n)$ and $g(n)$ . Regrouping the terms is the whole argument, and it is why the solution set behaves like a plane through the origin rather than a scattered collection.

Proof.

Let $n \geqslant d$ . Using the definition of $h$ , then the hypotheses on $f$ and $g$ ,

\begin{aligned} a_1 h(n-1) + \cdots + a_d h(n-d) &= a_1\bigl(sf(n-1) + tg(n-1)\bigr) + \cdots + a_d\bigl(sf(n-d) + tg(n-d)\bigr) \\ &= s\bigl(a_1 f(n-1) + \cdots + a_d f(n-d)\bigr) + t\bigl(a_1 g(n-1) + \cdots + a_d g(n-d)\bigr) \\ &= s f(n) + t g(n) = h(n). \end{aligned}

Linear recurrences tend to have exponential solutions, so we look for one of the form $f(n) = x^n$ and let the recurrence decide which $x$ will serve. Substituting into $f(n) = f(n-1) + f(n-2)$ gives $x^n = x^{n-1} + x^{n-2}$ , and dividing by $x^{n-2}$ , which is legitimate since $x = 0$ does not satisfy the boundary conditions, leaves

x^2 = x + 1 .

Its roots are

\varphi = \frac{1 + \sqrt{5}}{2} = 1.618\ldots, \qquad \hat{\varphi} = \frac{1 - \sqrt{5}}{2} = -0.618\ldots,

so $\varphi^n$ and $\hat{\varphi}^n$ both satisfy the recurrence, and by the theorem above so does $s\varphi^n + t\hat{\varphi}^n$ for every $s$ and $t$ . Two constants are exactly what two boundary conditions can pin down.

Definition 2.6 (Characteristic equation).

The characteristic equation of the homogeneous linear recurrence $f(n) = a_1f(n-1) + \cdots + a_df(n-d)$ is

x^d = a_1 x^{d-1} + a_2 x^{d-2} + \cdots + a_{d-1}x + a_d ,

obtained by substituting $f(n) = x^n$ and dividing by $x^{n-d}$ . Its coefficients are read straight off the recurrence.

Theorem 2.7 (Binet's formula).

Let $f$ satisfy $f(0) = f(1) = 1$ and $f(n) = f(n-1) + f(n-2)$ for $n \geqslant 2$ . Then for every $n \in \mathbb{N}_0$ ,

f(n) = \frac{1}{\sqrt{5}}\left( \varphi^{\,n+1} - \hat{\varphi}^{\,n+1} \right), \qquad \varphi = \frac{1 + \sqrt{5}}{2}, \quad \hat{\varphi} = \frac{1 - \sqrt{5}}{2}.

Discussion.

The two exponentials $\varphi^n$ and $\hat\varphi^n$ satisfy the recurrence because $\varphi$ and $\hat\varphi$ solve the characteristic equation, and the previous theorem then makes every combination $s\varphi^n + t\hat\varphi^n$ a solution as well. What remains is to choose $s$ and $t$ so that the combination also meets the two boundary conditions, and each condition is one linear equation in the two unknowns. Solving the pair is routine once one notices that $\varphi - \hat\varphi = \sqrt5$ and $1 - \hat\varphi = \varphi$ , which is what turns the answer into a single difference of powers. Since the recurrence and the two boundary conditions determine $f$ at every point, a function meeting all three is the function.

Proof.

Both $\varphi$ and $\hat\varphi$ satisfy $x^2 = x + 1$ , so multiplying by $x^{n-2}$ shows that $\varphi^n$ and $\hat\varphi^n$ satisfy the recurrence; by the previous theorem so does $h(n) = s\varphi^n + t\hat\varphi^n$ for any reals $s, t$ .

The boundary conditions require $h(0) = 1$ and $h(1) = 1$ , that is

s + t = 1, \qquad s\varphi + t\hat\varphi = 1 .

Substituting $t = 1 - s$ into the second gives $s(\varphi - \hat\varphi) = 1 - \hat\varphi$ . Now $\varphi - \hat\varphi = \sqrt5$ and $1 - \hat\varphi = \tfrac{1}{2}(1 + \sqrt5) = \varphi$ , so $s = \varphi/\sqrt5$ ; and then $t = 1 - \varphi/\sqrt5 = (\sqrt5 - \varphi)/\sqrt5 = -\hat\varphi/\sqrt5$ , since $\sqrt5 - \varphi = \tfrac{1}{2}(\sqrt5 - 1) = -\hat\varphi$ . Therefore

h(n) = \frac{\varphi}{\sqrt5}\varphi^n - \frac{\hat\varphi}{\sqrt5}\hat\varphi^n = \frac{1}{\sqrt5}\left(\varphi^{\,n+1} - \hat\varphi^{\,n+1}\right).

The recurrence together with the values at $0$ and $1$ determines $f(n)$ for every $n$ , and $h$ satisfies all three, so $f = h$ .

Remark (Integers out of square roots).

Every value of $f$ is a whole number, yet the formula is built entirely from $\sqrt5$ ; the irrational parts cancel at every $n$ . Since $|\hat\varphi| < 1$ the second term is smaller than $\tfrac12$ in absolute value at every $n$ , so $f(n)$ is the nearest integer to $\varphi^{\,n+1}/\sqrt5$ throughout. For instance $\varphi^{20}/\sqrt5 = 6765.000029\ldots$ , and $f(19) = 6765$ . The same estimate shows that consecutive values have ratio tending to $\varphi$ , the golden ratio.

Example 2.8 (A recurrence of order two).

Let $f(0) = 0$ , $f(1) = 1$ and $f(n) = 5f(n-1) - 6f(n-2)$ for $n \geqslant 2$ . The characteristic equation is $x^2 = 5x - 6$ , that is $(x-2)(x-3) = 0$ , with roots $2$ and $3$ . So $f(n) = s\,2^n + t\,3^n$ , and the boundary conditions give $s + t = 0$ and $2s + 3t = 1$ , whence $t = 1$ and $s = -1$ . Therefore $f(n) = 3^n - 2^n$ .

When the characteristic equation has a repeated root, the powers of that root alone do not supply enough independent solutions, and the missing ones carry a factor of $n$ .

Proposition 2.9 (Repeated roots).

Let $r \neq 0$ be a root of multiplicity at least $2$ of the characteristic equation of a homogeneous linear recurrence. Then $f(n) = n r^n$ satisfies the recurrence.

Discussion.

Saying that $r$ is a root of multiplicity at least two means that the characteristic polynomial and its derivative both vanish at $r$ , and the factor of $n$ in the claimed solution is exactly what a derivative produces from a power. So the proof multiplies the characteristic polynomial by $x^{n-d}$ to obtain a polynomial whose vanishing at $r$ is the statement that $r^n$ solves the recurrence, differentiates it, and multiplies by $x$ ; the result, evaluated at $r$ , is precisely the statement that $nr^n$ solves the recurrence. The hypothesis $r \neq 0$ is what lets the multiplicity survive the multiplication by $x^{n-d}$ .

Proof.

Write $p(x) = x^d - a_1x^{d-1} - \cdots - a_d$ for the characteristic polynomial and fix $n \geqslant d$ . Put

q(x) = x^{n-d}p(x) = x^n - a_1x^{n-1} - \cdots - a_d x^{n-d} .

Since $r \neq 0$ is a root of $p$ of multiplicity at least $2$ , it is a root of $q$ of multiplicity at least $2$ , so $q(r) = 0$ and $q'(r) = 0$ . Differentiating,

q'(x) = n x^{n-1} - a_1(n-1)x^{n-2} - \cdots - a_d(n-d)x^{n-d-1},

and multiplying by $x$ ,

x\,q'(x) = n x^{n} - a_1(n-1)x^{n-1} - \cdots - a_d(n-d)x^{n-d} .

Evaluating at $x = r$ and using $q'(r) = 0$ gives

n r^n = a_1 (n-1) r^{n-1} + \cdots + a_d (n-d) r^{n-d},

which says exactly that $f(n) = nr^n$ satisfies the recurrence.

More generally, a root $r$ of multiplicity $k$ contributes the $k$ solutions $r^n$ , $nr^n$ , $n^2r^n$ , up to $n^{k-1}r^n$ , and a recurrence of order $d$ is solved by taking a linear combination of the $d$ solutions collected in this way from all the roots. If the characteristic equation of an order-four recurrence has roots $s$ , $t$ and $u$ twice, the general solution is

f(n) = a\,s^n + b\,t^n + c\,u^n + d\,n\,u^n,

and four boundary conditions give four linear equations in $a, b, c, d$ .

Inhomogeneous Recurrences

The Hanoi recurrence $f(n) = 2f(n-1) + 1$ is not homogeneous: the extra $1$ is a term $g(n)$ on the right. Such recurrences are solved in five steps.

Delete $g(n)$ and find the roots of the characteristic equation of what is left.
Write down the general solution of that homogeneous recurrence, leaving its constants undetermined. This is the homogeneous solution.
Restore $g(n)$ and find any one function satisfying the full recurrence, ignoring the boundary conditions. This is a particular solution.
Add the two. This is the general solution.
Use the boundary conditions to fix the constants.

Example 2.10 (Hanoi with heavy discs).

Suppose moving a disc costs its size in seconds, so that moving the $n$ th disc takes $n$ seconds rather than one. The total time obeys

f(1) = 1, \qquad f(n) = 2f(n-1) + n \quad (n \geqslant 2).

Deleting the $n$ leaves $f(n) = 2f(n-1)$ , whose characteristic equation is $x = 2$ , so the homogeneous solution is $c\,2^n$ .

For a particular solution, $g(n) = n$ is a polynomial of degree one, so try $f(n) = an + b$ . Substituting,

an + b = 2\bigl(a(n-1) + b\bigr) + n \quad\Longleftrightarrow\quad 0 = (a+1)n + (b - 2a),

which holds for every $n$ exactly when $a = -1$ and $b = -2$ . So $-n-2$ is a particular solution and the general solution is $f(n) = c\,2^n - n - 2$ .

The boundary condition $f(1) = 1$ gives $2c - 3 = 1$ , so $c = 2$ and

f(n) = 2^{\,n+1} - n - 2 .

Against $2^n - 1$ for the original puzzle, the heavy discs cost roughly twice as long.

Remark (Guessing a particular solution).

Finding a particular solution is the one step that involves a guess, and the guess is usually shaped like $g(n)$ itself.

If $g(n)$ is constant, try $f(n) = c$ ; if that fails, try $bn + c$ , then $an^2 + bn + c$ , and so on. If $g(n)$ is a polynomial, try a polynomial of the same degree first and then of higher degree. If $g(n)$ is an exponential such as $3^n$ , try $f(n) = c\,3^n$ , then $bn3^n + c3^n$ , and so on. A guess fails when substituting it leaves an equation with no constant solution, and raising the degree by one is then the next move.

Problem 2.7.

Solve $f(0) = 0$ , $f(1) = 1$ , $f(n) = 4f(n-1) - 4f(n-2)$ for $n \geqslant 2$ . (The characteristic equation has a repeated root.)

Problem 2.8.

Solve $f(0) = 1$ and $f(n) = 3f(n-1) + 2^n$ for $n \geqslant 1$ .

Problem 2.9.

Let $r$ be a root of multiplicity at least $3$ of the characteristic equation of a homogeneous linear recurrence, with $r \neq 0$ . Prove that $n^2 r^n$ satisfies the recurrence.

Problem 2.10.

How many ways are there to climb $n$ stairs if a stride may go up one, two or three steps? Write down the recurrence, its characteristic equation, and compute the number of ways for $n \leqslant 6$ .

Problem 2.11.

Let $f$ satisfy the Fibonacci recurrence with $f(0) = f(1) = 1$ . Prove that $f(n)$ is the nearest integer to $\varphi^{\,n+1}/\sqrt{5}$ for every $n \geqslant 1$ .

The Josephus Problem

Flavius Josephus, a first-century historian, was said to have been trapped in a cave with forty-one other rebels who preferred death to capture and agreed to stand in a circle and kill every third man. Josephus worked out where to stand.

The version we take is this. Number $n$ people $1$ to $n$ around a circle and go round eliminating every second person until one is left. Which number survives? Call it $J(n)$ .

Figure 2.3. Ten people in a circle. Eliminating every second one leaves number

5

, so

J(10) = 5

Proposition 2.11 (The Josephus recurrence).

For every $\ell \in \mathbb{N}$ ,

J(2\ell) = 2J(\ell) - 1, \qquad J(2\ell + 1) = 2J(\ell) + 1,

and $J(1) = 1$ .

Discussion.

One person survives trivially. For the rest, the point is that after one lap of the circle exactly the even-numbered people have gone, and what is left is a circle of half the size with the same rule about to be applied to it. So the problem of size $n$ reduces to the problem of size $\lfloor n/2 \rfloor$ , and all that is needed is the dictionary between the numbering of the survivors and their original numbers. The two cases differ only in where the second lap starts. If $n$ is even the lap ends by killing person $n$ and the next to die is the second of the survivors; if $n$ is odd the lap ends by killing person $n-1$ , then person $1$ dies immediately, and the survivors start from person $3$ . Reading off the $k$ th survivor’s original number in each case, $2k-1$ and $2k+1$ , converts $J(\ell)$ into $J(n)$ .

Proof.

With one person there is nobody to eliminate, so $J(1) = 1$ .

Suppose $n = 2\ell$ with $\ell \in \mathbb{N}$ . Going round once eliminates $2, 4, \ldots, 2\ell$ and leaves the $\ell$ odd-numbered people $1, 3, \ldots, 2\ell - 1$ , with the next elimination falling on the second of them. So what remains is the same problem for $\ell$ people, counted from $1$ , and the $k$ th of those people carries the original number $2k - 1$ . The survivor is the $J(\ell)$ th of them, so its original number is $2J(\ell) - 1$ .

Suppose instead $n = 2\ell + 1$ with $\ell \in \mathbb{N}$ . Going round once eliminates $2, 4, \ldots, 2\ell$ ; the count then passes from $2\ell+1$ to $1$ , which is eliminated next. That leaves the $\ell$ people $3, 5, \ldots, 2\ell + 1$ , with the next elimination falling on the second of them. Again this is the problem for $\ell$ people, and the $k$ th of them carries the original number $2k + 1$ . The survivor is therefore numbered $2J(\ell) + 1$ .

Tabulating the first sixteen values, grouped by powers of two, makes the pattern plain:

\begin{array}{c|cc|cccc|cccccccc|c} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ \hline J(n) & 1 & 1 & 3 & 1 & 3 & 5 & 7 & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 1 \end{array}

Each block begins at $1$ when $n$ reaches a power of two and climbs through the odd numbers. That suggests measuring $n$ from the power of two below it.

Theorem 2.12 (Closed form for the Josephus problem).

Let $n \in \mathbb{N}$ and write $n = 2^m + r$ where $2^m$ is the largest power of two with $2^m \leqslant n$ , so that $m \geqslant 0$ and $0 \leqslant r < 2^m$ . Then

J(n) = 2r + 1 .

Discussion.

The recurrence takes $n$ to $\lfloor n/2 \rfloor$ , so the proof is an induction in which the inductive hypothesis is applied at a smaller value rather than at the immediate predecessor; strong induction on $n$ is what fits. Everything then turns on how the decomposition $n = 2^m + r$ behaves under halving. If $n$ is even then $r$ is even too, since $r = n - 2^m$ and $m \geqslant 1$ , and halving $n$ gives $2^{m-1} + r/2$ with the remainder still in range. If $n$ is odd then $r$ is odd, and $\lfloor n/2 \rfloor = 2^{m-1} + (r-1)/2$ , again in range. In both cases the hypothesis supplies the survivor for the halved circle, and the two clauses of the recurrence turn it into $2r+1$ ; the arithmetic works out to the same answer either way, which is why the formula has no cases in it.

Proof.

We induct on $n$ , assuming the claim for all smaller values.

If $n = 1$ then $m = 0$ and $r = 0$ , and $J(1) = 1 = 2 \cdot 0 + 1$ .

Let $n \geqslant 2$ and write $n = 2^m + r$ with $0 \leqslant r < 2^m$ ; since $n \geqslant 2$ we have $m \geqslant 1$ .

Suppose $n$ is even, say $n = 2\ell$ . Then $r = n - 2^m$ is even, and

\ell = \frac{n}{2} = 2^{m-1} + \frac{r}{2}, \qquad 0 \leqslant \frac{r}{2} < 2^{m-1},

so the decomposition of $\ell$ has exponent $m-1$ and remainder $r/2$ . As $\ell < n$ , the inductive hypothesis gives $J(\ell) = 2(r/2) + 1 = r + 1$ , and the recurrence gives

J(n) = 2J(\ell) - 1 = 2(r+1) - 1 = 2r + 1 .

Suppose instead $n$ is odd, say $n = 2\ell + 1$ with $\ell \geqslant 1$ . Then $r = n - 2^m$ is odd, and

\ell = \frac{n-1}{2} = 2^{m-1} + \frac{r-1}{2}, \qquad 0 \leqslant \frac{r-1}{2} < 2^{m-1},

the upper bound because $r < 2^m$ forces $r - 1 < 2^m - 1$ and hence $(r-1)/2 < 2^{m-1}$ . The inductive hypothesis gives $J(\ell) = 2\cdot\frac{r-1}{2} + 1 = r$ , and the recurrence gives

J(n) = 2J(\ell) + 1 = 2r + 1 .

Reading the Answer in Binary

The decomposition $n = 2^m + r$ is exactly what binary notation records. Writing

n = (1\,b_{m-1}\,b_{m-2}\cdots b_1\,b_0)_2

with leading digit $1$ , the remainder is $r = (0\,b_{m-1}\cdots b_1\,b_0)_2$ , so $2r = (b_{m-1}\cdots b_1\,b_0\,0)_2$ and

J(n) = 2r + 1 = (b_{m-1}\,b_{m-2}\cdots b_1\,b_0\,1)_2 .

Since the leading digit that was dropped is a $1$ , the answer is obtained from $n$ by moving its leading digit to the end: a one-bit cyclic shift to the left.

Example 2.13 (A cyclic shift).

Take $n = 100 = (1100100)_2$ . Shifting the leading digit round to the end gives $(1001001)_2 = 73$ , so $J(100) = 73$ . Checking against the closed form, $100 = 64 + 36$ , so $r = 36$ and $2r + 1 = 73$ .

Remark (Iterating the shift).

Applying $J$ repeatedly does not cycle back to $n$ after $m+1$ shifts, because $J(n) \leqslant n$ always, and once a value drops it can never climb again. What happens instead is that whenever the leading digit is a $0$ it is simply dropped, so each application deletes a zero. After enough applications only the ones remain, and the value settles at

(\underbrace{11\cdots1}_{\nu(n)})_2 = 2^{\nu(n)} - 1,

where $\nu(n)$ is the number of ones in the binary representation of $n$ . For instance $J(11) = J((1011)_2) = (111)_2 = 7$ , and $J(7) = 7$ .

Proposition 2.14 (When the survivor is halfway round).

Let $n = 2^m + r$ with $0 \leqslant r < 2^m$ . Then $J(n) = n/2$ if and only if $m$ is odd and $r = (2^m - 2)/3$ .

Discussion.

Substituting the closed form turns the condition $J(n) = n/2$ into a linear equation in $r$ and $2^m$ , and solving it gives $r = (2^m-2)/3$ outright, so the only question left is for which $m$ that number is an integer lying below $2^m$ . The bound is immediate. Integrality is a statement about $2^m$ modulo $3$ , and the powers of two alternate between $1$ and $2$ there, since doubling exchanges the two; so $2^m - 2$ is divisible by $3$ exactly for odd $m$ .

Proof.

By the closed form, $J(n) = n/2$ says $2r + 1 = (2^m + r)/2$ , that is $4r + 2 = 2^m + r$ , that is

3r = 2^m - 2, \qquad\text{so}\qquad r = \frac{2^m - 2}{3}.

This $r$ satisfies $r < 2^m$ automatically. It is an integer exactly when $2^m \equiv 2 \pmod 3$ . Now $2^0 = 1$ leaves remainder $1$ , and doubling a number that leaves remainder $1$ gives one that leaves remainder $2$ , while doubling a number that leaves remainder $2$ gives $4$ , which leaves remainder $1$ . So the remainders alternate $1, 2, 1, 2, \ldots$ as $m = 0, 1, 2, 3, \ldots$ , and $2^m \equiv 2$ exactly when $m$ is odd.

The first few such $n$ are

\begin{array}{c|c|c|c|c} m & r & n = 2^m + r & J(n) = n/2 & n \text{ in binary} \\ \hline 1 & 0 & 2 & 1 & 10 \\ 3 & 2 & 10 & 5 & 1010 \\ 5 & 10 & 42 & 21 & 101010 \\ 7 & 42 & 170 & 85 & 10101010 \end{array}

These are the $n$ for which shifting the leading bit to the end has the same effect as deleting the last bit.

The Repertoire Method

Guessing worked for the Josephus recurrence because its answers were small numbers with a visible pattern. When a guess is not available, the following method manufactures one. Consider the recurrence with three undetermined constants,

f(n) = \begin{cases} \alpha, & n = 1, \\ 2f(\ell) + \beta, & n = 2\ell, \; \ell \in \mathbb{N}, \\ 2f(\ell) + \gamma, & n = 2\ell + 1, \; \ell \in \mathbb{N}, \end{cases}

of which the Josephus recurrence is the case $\alpha = 1$ , $\beta = -1$ , $\gamma = 1$ . Its first few values are

\begin{array}{c|l} n & f(n) \\ \hline 1 & \alpha \\ 2 & 2\alpha + \beta \\ 3 & 2\alpha + \gamma \\ 4 & 4\alpha + 3\beta \\ 5 & 4\alpha + 2\beta + \gamma \\ 6 & 4\alpha + \beta + 2\gamma \\ 7 & 4\alpha + 3\gamma \\ 8 & 8\alpha + 7\beta \\ 9 & 8\alpha + 6\beta + \gamma \end{array}

Every entry is a combination of $\alpha$ , $\beta$ and $\gamma$ with coefficients depending only on $n$ , so we may write

f(n) = A(n)\,\alpha + B(n)\,\beta + C(n)\,\gamma ,

and the task becomes finding the three functions $A$ , $B$ , $C$ . The method is to substitute values of $\alpha, \beta, \gamma$ , or functions $f$ , for which the recurrence can be solved by inspection; each substitution yields one equation relating $A$ , $B$ and $C$ , and three independent equations determine them.

Proposition 2.15 (The coefficient of $\alpha$ ).

Let $n = 2^m + r$ with $0 \leqslant r < 2^m$ . Then $A(n) = 2^m$ .

Discussion.

Setting $\alpha = 1$ and $\beta = \gamma = 0$ makes $f(n)$ equal to $A(n)$ and collapses the recurrence to $A(1) = 1$ with $A(n) = 2A(\lfloor n/2 \rfloor)$ in both the even and the odd case. That recurrence doubles once per halving and never distinguishes the two cases, so it depends on $n$ only through how often $n$ can be halved, which is $m$ . The induction is the same strong induction as before, using that $\lfloor n/2 \rfloor$ has exponent $m - 1$ in its own decomposition.

Proof.

Putting $\alpha = 1$ and $\beta = \gamma = 0$ gives $f = A$ and

A(1) = 1, \qquad A(2\ell) = 2A(\ell), \qquad A(2\ell+1) = 2A(\ell) .

We induct on $n$ . For $n = 1$ we have $m = 0$ and $A(1) = 1 = 2^0$ . For $n \geqslant 2$ write $n = 2^m + r$ with $m \geqslant 1$ , and put $\ell = \lfloor n/2 \rfloor$ . As in the proof of the closed form for $J$ , the decomposition of $\ell$ has exponent $m-1$ , whichever parity $n$ has. Both clauses of the recurrence give $A(n) = 2A(\ell)$ , and the inductive hypothesis gives $A(\ell) = 2^{m-1}$ , so $A(n) = 2^m$ .

Two more substitutions finish the job, and this time we choose the function rather than the constants.

Take $f(n) = 1$ for every $n$ . The three clauses become $1 = \alpha$ , $1 = 2 + \beta$ and $1 = 2 + \gamma$ , so this constant function is the solution for $\alpha = 1$ , $\beta = \gamma = -1$ . Substituting those values into $f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma$ gives

1 = A(n) - B(n) - C(n) .

Take $f(n) = n$ . The clauses become $1 = \alpha$ , $2\ell = 2\ell + \beta$ and $2\ell + 1 = 2\ell + \gamma$ , so this is the solution for $\alpha = 1$ , $\beta = 0$ , $\gamma = 1$ , and

n = A(n) + C(n) .

Now solve. From $A(n) = 2^m$ and $A(n) + C(n) = n = 2^m + r$ we get $C(n) = r$ ; and then $B(n) = A(n) - C(n) - 1 = 2^m - 1 - r$ .

Theorem 2.16 (Solution of the generalised Josephus recurrence).

Let $\alpha, \beta, \gamma$ be constants and let $f$ satisfy the recurrence above. Then for $n = 2^m + r$ with $0 \leqslant r < 2^m$ ,

f(n) = 2^m \alpha + \bigl(2^m - 1 - r\bigr)\beta + r\gamma .

Discussion.

The repertoire method produced this formula but did not prove it, since it assumed at the outset that $f(n)$ is a combination of $\alpha$ , $\beta$ and $\gamma$ with coefficients independent of them. That assumption is easy to justify after the fact: the right-hand side is a specific function of $n$ , so it is enough to check that it satisfies the three clauses of the recurrence, and a solution of the recurrence is unique because the clauses determine $f(n)$ from $f(\lfloor n/2 \rfloor)$ and $f(1)$ is given. The verification is the same case split on the parity of $n$ used twice already, with the decomposition of $\lfloor n/2 \rfloor$ read off as before.

Proof.

Write $F(2^m + r) = 2^m\alpha + (2^m - 1 - r)\beta + r\gamma$ for $0 \leqslant r < 2^m$ . Since the clauses determine $f(n)$ from $f(\lfloor n/2\rfloor)$ for $n \geqslant 2$ and fix $f(1)$ , at most one function satisfies them; so it suffices to check that $F$ does.

At $n = 1$ we have $m = r = 0$ and $F(1) = \alpha$ .

Let $n = 2\ell \geqslant 2$ , so $m \geqslant 1$ and $r$ is even, and $\ell = 2^{m-1} + r/2$ with $0 \leqslant r/2 < 2^{m-1}$ . Then

2F(\ell) + \beta = 2\left[2^{m-1}\alpha + \left(2^{m-1} - 1 - \tfrac{r}{2}\right)\beta + \tfrac{r}{2}\gamma\right] + \beta = 2^m\alpha + \bigl(2^m - 2 - r + 1\bigr)\beta + r\gamma,

which is $F(n)$ .

Let $n = 2\ell + 1 \geqslant 3$ , so $m \geqslant 1$ and $r$ is odd, and $\ell = 2^{m-1} + (r-1)/2$ with $0 \leqslant (r-1)/2 < 2^{m-1}$ . Then

2F(\ell) + \gamma = 2\left[2^{m-1}\alpha + \left(2^{m-1} - 1 - \tfrac{r-1}{2}\right)\beta + \tfrac{r-1}{2}\gamma\right] + \gamma = 2^m\alpha + \bigl(2^m - 1 - r\bigr)\beta + r\gamma,

which is $F(n)$ again.

Setting $\alpha = 1$ , $\beta = -1$ , $\gamma = 1$ recovers $2^m - (2^m - 1 - r) + r = 2r + 1$ , the Josephus answer.

Radix Notation

The generalised recurrence has a shorter description if the two constants added at each step are indexed by the bit that decides between them. Write $\beta_0 = \beta$ and $\beta_1 = \gamma$ ; then the three clauses become

f(1) = \alpha, \qquad f(2\ell + j) = 2f(\ell) + \beta_j \quad (j \in \{0, 1\}),

and $j$ is the last binary digit of $n$ . Unrolling the second clause strips one digit at a time:

\begin{aligned} f\bigl((1\,b_{m-1}\cdots b_1 b_0)_2\bigr) &= 2 f\bigl((1\,b_{m-1}\cdots b_1)_2\bigr) + \beta_{b_0} \\ &= 4 f\bigl((1\,b_{m-1}\cdots b_2)_2\bigr) + 2\beta_{b_1} + \beta_{b_0} \\ &\;\;\vdots \\ &= 2^m \alpha + 2^{m-1}\beta_{b_{m-1}} + \cdots + 2\beta_{b_1} + \beta_{b_0} . \end{aligned}

The right-hand side has the shape of a binary expansion whose digits are the constants rather than $0$ and $1$ , so we write it

f(n) = \bigl(\alpha\;\beta_{b_{m-1}}\;\beta_{b_{m-2}}\cdots\beta_{b_1}\;\beta_{b_0}\bigr)_2 ,

meaning that each entry is multiplied by the appropriate power of two and the results added. Recovering the earlier table is a matter of reading off digits: $6 = (110)_2$ gives $2^2\alpha + 2\gamma + \beta$ , and $9 = (1001)_2$ gives $2^3\alpha + 2^2\beta + 2\beta + \gamma$ .

Example 2.17 (The Josephus survivor for $n = 100$ ).

With $\alpha = 1$ , $\beta_0 = -1$ and $\beta_1 = 1$ , and $100 = (1100100)_2$ ,

\begin{aligned} J(100) &= 2^6(1) + 2^5(1) + 2^4(-1) + 2^3(-1) + 2^2(1) + 2(-1) + (-1) \\ &= 64 + 32 - 16 - 8 + 4 - 2 - 1 = 73 , \end{aligned}

agreeing with the cyclic shift $(1100100)_2 \mapsto (1001001)_2$ .

Nothing in the argument used the base $2$ or the multiplier $2$ separately, and separating them gives the general statement.

Theorem 2.18 (Recurrences that strip a digit).

Let $d \geqslant 2$ and $c$ be constants, let $\alpha_1, \ldots, \alpha_{d-1}$ and $\beta_0, \ldots, \beta_{d-1}$ be constants, and let $f$ satisfy

f(i) = \alpha_i \quad (1 \leqslant i \leqslant d-1), \qquad f(dn + j) = c\,f(n) + \beta_j \quad (n \geqslant 1, \; 0 \leqslant j < d).

Then for $n = (b_m\,b_{m-1}\cdots b_1\,b_0)_d$ with $b_m \neq 0$ ,

f(n) = \bigl(\alpha_{b_m}\;\beta_{b_{m-1}}\cdots\beta_{b_1}\;\beta_{b_0}\bigr)_c = c^m \alpha_{b_m} + c^{m-1}\beta_{b_{m-1}} + \cdots + c\,\beta_{b_1} + \beta_{b_0}.

Discussion.

The second clause consumes exactly one base- $d$ digit of its argument, because writing $n = dn' + j$ with $0 \leqslant j < d$ is the same as splitting off the last digit $b_0 = j$ and leaving $n' = (b_m \cdots b_1)_d$ . So each application of the clause peels a digit and multiplies what has accumulated by $c$ , and after $m$ applications the argument has been reduced to its leading digit $b_m$ , which lies between $1$ and $d-1$ and is therefore covered by the first clause. The proof is an induction on the number of digits, and the only thing to check carefully is that the split of $n$ into $dn' + j$ really does correspond to the split of the digit string, which is where the uniqueness of base- $d$ representation is used.

Proof.

We induct on $m$ , the number of digits after the leading one.

If $m = 0$ then $n = b_0$ with $1 \leqslant b_0 \leqslant d-1$ , and the first clause gives $f(n) = \alpha_{b_0}$ , which is the claim.

Let $m \geqslant 1$ and write $n = (b_m \cdots b_1 b_0)_d$ , that is

n = b_m d^m + b_{m-1}d^{m-1} + \cdots + b_1 d + b_0 = d\bigl(b_m d^{m-1} + \cdots + b_1\bigr) + b_0 .

Setting $n' = (b_m \cdots b_1)_d$ and $j = b_0$ , we have $n = dn' + j$ with $0 \leqslant j < d$ and $n' \geqslant 1$ . The second clause and the inductive hypothesis applied to $n'$ , which has $m-1$ digits after its leading one, give

f(n) = c\,f(n') + \beta_{b_0} = c\left(c^{m-1}\alpha_{b_m} + c^{m-2}\beta_{b_{m-1}} + \cdots + \beta_{b_1}\right) + \beta_{b_0},

and expanding the bracket is the claim at $m$ .

Representation in a Base

The theorem above took for granted that $n$ has a base- $d$ digit string and that the string is determined by $n$ . Both facts need proof, and the tools are the floor function and the remainder.

Definition 2.19 (Floor, ceiling and remainder).

For $x \in \mathbb{R}$ ,

\lfloor x \rfloor = \max\{k \in \mathbb{Z} \mid k \leqslant x\}, \qquad \lceil x \rceil = \min\{k \in \mathbb{Z} \mid k \geqslant x\} .

For $x \in \mathbb{Z}$ and $y \in \mathbb{N}$ the remainder of $x$ on division by $y$ is

x \bmod y = x - y\left\lfloor \frac{x}{y} \right\rfloor .

Rearranging the last definition gives the identity we shall use repeatedly: for $z \in \mathbb{N}_0$ and $b \in \mathbb{N}$ ,

z = b\left\lfloor \frac{z}{b} \right\rfloor + (z \bmod b), \qquad 0 \leqslant z \bmod b < b .

Example 2.20 (Floors and remainders).

$\lfloor 13.2 \rfloor = 13$ and $\lceil 13.2 \rceil = 14$ . For the remainder,

23 \bmod 6 = 23 - 6\left\lfloor \tfrac{23}{6} \right\rfloor = 23 - 6 \cdot 3 = 5, \qquad 23 = 3 \cdot 6 + 5 .

Theorem 2.21 (Representation in a base).

Let $b, n \in \mathbb{N}$ with $b > 1$ . Every $z \in \mathbb{N}_0$ with $0 \leqslant z \leqslant b^n - 1$ can be written as

z = \sum_{i=0}^{n-1} z_i b^i, \qquad z_i \in \{0, 1, \ldots, b-1\},

and the digits $z_0, \ldots, z_{n-1}$ are uniquely determined by $z$ .

Discussion.

There are two claims, and they are proved by different means.

Existence is an induction on the number of digits $n$ , and the step is division by $b$ . Given $z$ below $b^{n+1}$ , split it as $z = b\hat{z} + z_0$ with $z_0 = z \bmod b$ the last digit and $\hat{z} = \lfloor z/b \rfloor$ what remains. The point to check is that $\hat{z}$ falls in the range the inductive hypothesis covers, namely below $b^n$ , and it does because dividing by $b$ shrinks the bound by a factor of $b$ . The hypothesis then supplies $n$ digits for $\hat{z}$ , and multiplying the whole expansion by $b$ shifts every digit up one place, leaving room at the bottom for $z_0$ .

Uniqueness is an argument by contradiction that needs no induction. Suppose two different digit strings give the same value, and look at the highest place $m$ where they disagree. Above $m$ the terms are equal and cancel, so the difference of the two sums is a single term $(z_m - \hat{z}_m)b^m$ , which is at least $b^m$ , plus lower terms, each of which is at least $-(b-1)b^i$ . Summing those lower bounds telescopes to $1 - b^m$ , so the total is at least $b^m + 1 - b^m = 1$ ; but the total is $0$ . The heart of it is that one unit in a place outweighs everything below it, which is what makes positional notation work at all.

Proof.

Existence. We induct on $n$ .

For $n = 0$ the only $z$ in range is $z = 0$ , represented by the empty sum.

Suppose every $\hat{z}$ with $0 \leqslant \hat{z} \leqslant b^n - 1$ has a representation with $n$ digits, and let $0 \leqslant z \leqslant b^{n+1} - 1$ . Put

z_0 = z \bmod b, \qquad \hat{z} = \left\lfloor \frac{z}{b} \right\rfloor, \qquad\text{so}\qquad z = b\hat{z} + z_0, \quad 0 \leqslant z_0 < b .

We check that $\hat{z}$ lies in the range covered by the hypothesis. From $z \leqslant b^{n+1} - 1 < b^{n+1}$ we get $z/b < b^n$ , and $\hat z \leqslant z/b$ , so $\hat{z} < b^n$ ; being an integer, $\hat{z} \leqslant b^n - 1$ . Also $\hat{z} \geqslant 0$ . So the hypothesis applies and gives digits $\hat{z}_0, \ldots, \hat{z}_{n-1}$ in $\{0, \ldots, b-1\}$ with $\hat{z} = \sum_{i=0}^{n-1}\hat{z}_i b^i$ . Then

z = b\sum_{i=0}^{n-1}\hat{z}_i b^i + z_0 = \sum_{i=0}^{n-1}\hat{z}_i b^{i+1} + z_0 = \sum_{i=1}^{n}\hat{z}_{i-1} b^{i} + z_0 = \sum_{i=0}^{n} z_i b^i,

where the third step reindexed the sum by $i \mapsto i+1$ and the last set $z_i = \hat{z}_{i-1}$ for $1 \leqslant i \leqslant n$ , with $z_0$ as chosen. Every digit lies in $\{0, \ldots, b-1\}$ , and there are $n+1$ of them, which is the claim for $n+1$ .

Uniqueness. Suppose

\sum_{i=0}^{n-1} z_i b^i = \sum_{i=0}^{n-1} \hat{z}_i b^i

with all digits in $\{0, \ldots, b-1\}$ , and suppose the two strings are not identical. Let

m = \max\{\, i \mid 0 \leqslant i \leqslant n-1, \; z_i \neq \hat{z}_i \,\},

and assume without loss of generality that $z_m > \hat{z}_m$ . All terms with $i > m$ agree and cancel, so subtracting one sum from the other leaves

0 = \sum_{i=0}^{m} (z_i - \hat{z}_i)\,b^i = (z_m - \hat{z}_m)\,b^m + \sum_{i=0}^{m-1}(z_i - \hat{z}_i)\,b^i .

Now bound the two pieces from below. The digits are integers with $z_m > \hat z_m$ , so $z_m - \hat{z}_m \geqslant 1$ and the first term is at least $b^m$ . For $i < m$ we have $z_i \geqslant 0$ and $\hat{z}_i \leqslant b-1$ , so $z_i - \hat{z}_i \geqslant 1 - b$ and

\sum_{i=0}^{m-1}(z_i - \hat{z}_i)\,b^i \;\geqslant\; (1-b)\sum_{i=0}^{m-1} b^i = \sum_{i=0}^{m-1}b^i - \sum_{i=0}^{m-1}b^{i+1} = \sum_{i=0}^{m-1}b^i - \sum_{i=1}^{m}b^{i} = b^0 - b^m,

the last step because the two sums share every term with $1 \leqslant i \leqslant m-1$ . Adding the two bounds,

0 \;\geqslant\; b^m + \bigl(1 - b^m\bigr) = 1,

which is false. So no two distinct digit strings represent the same $z$ .

Corollary 2.22 (Radix notation).

Let $b > 1$ . For a digit string $z_{n-1}, \ldots, z_0$ with entries in $\{0, \ldots, b-1\}$ write

(z_{n-1}\,z_{n-2}\cdots z_1\,z_0)_b = \sum_{i=0}^{n-1} z_i b^i .

Then every $z \in \mathbb{N}$ is $(z_{n-1}\cdots z_0)_b$ for exactly one digit string with leading digit $z_{n-1} \neq 0$ , and its length is $n = \lfloor \log_b z \rfloor + 1$ .

Proof.

Let $z \in \mathbb{N}$ and put $n = \lfloor \log_b z \rfloor + 1$ , so that $n - 1 \leqslant \log_b z < n$ and hence $b^{n-1} \leqslant z < b^n$ . The theorem applies with this $n$ and gives digits $z_0, \ldots, z_{n-1}$ , unique for this length. The leading digit is not zero: if $z_{n-1} = 0$ then $z = \sum_{i=0}^{n-2}z_ib^i \leqslant (b-1)\sum_{i=0}^{n-2}b^i = b^{n-1} - 1$ , contradicting $z \geqslant b^{n-1}$ .

Conversely, suppose $z = (z_{n'-1}\cdots z_0)_b$ for some length $n'$ with $z_{n'-1} \neq 0$ . Then $z \geqslant b^{n'-1}$ , and also $z \leqslant (b-1)\sum_{i=0}^{n'-1}b^i = b^{n'} - 1 < b^{n'}$ . So $b^{n'-1} \leqslant z < b^{n'}$ , which forces $n' = n$ , and the theorem then makes the digits the ones already found.

Remark (Horner's scheme).

Evaluating $(z_{n-1}\cdots z_0)_b$ by computing each power $b^i$ and multiplying costs about $2n$ multiplications. Nesting the expression,

\sum_{i=0}^{n-1} z_i b^i = z_0 + b\Bigl(z_1 + b\bigl(z_2 + \cdots + b(z_{n-2} + b\,z_{n-1})\cdots\bigr)\Bigr),

evaluates it from the inside out with $n-1$ multiplications and $n-1$ additions, and never forms a power of $b$ explicitly. This is Horner’s scheme, and the same nesting evaluates any polynomial at any point.

Problem 2.12.

Compute $J(1000)$ two ways, from the closed form and from the cyclic shift, and check that they agree.

Problem 2.13.

Show that $J(n) = n$ if and only if $n = 2^k - 1$ for some $k \in \mathbb{N}_0$ .

Problem 2.14.

For which $n$ does person $1$ survive? Show that person $2$ never survives, whatever $n$ may be.

Problem 2.15.

Use the repertoire method to solve

f(1) = \alpha, \qquad f(2\ell) = 3f(\ell) + \beta, \qquad f(2\ell + 1) = 3f(\ell) + \gamma .

Problem 2.16.

Write $\nu(n)$ for the number of ones in the binary representation of $n$ . Prove that repeated application of $J$ to any $n \in \mathbb{N}$ eventually reaches $2^{\nu(n)} - 1$ and stays there.

Problem 2.17.

Let $b > 1$ and $k \in \mathbb{N}$ . Show that the last $k$ digits of $z \in \mathbb{N}$ in base $b$ are the digits of $z \bmod b^{k}$ , padded with leading zeros if need be.

Sums

A recurrence adds one term to what came before, so every recurrence of the form $S_n = S_{n-1} + a_n$ is a sum in disguise and every sum is such a recurrence. This chapter sets up the notation for sums, establishes the laws that let them be rearranged, and turns the correspondence with recurrences into a method that evaluates sums the previous chapter could not touch.

Sequences

Definition 2.23 (Sequence).

A sequence of elements of a set $A$ is a function $f : \mathbb{N}_0 \to A$ . The value $f(n)$ is the $n$ th term and is written $a_n$ , and the sequence itself is written

\{a_n\}_{n \in \mathbb{N}_0}, \qquad \text{or } \{a_n\} \text{ when the index set is understood.}

The function and the list of its values are the same object seen two ways. Defining $f : \mathbb{N}_0 \to \mathbb{R}$ by $f(n) = n + \sqrt{n}$ is the same as writing $a_n = n + \sqrt{n}$ , and the same again as writing out

0, \quad 2, \quad 2 + \sqrt{2}, \quad 3 + \sqrt{3}, \quad \ldots, \quad n + \sqrt{n}, \quad \ldots

A sequence in this sense is infinite, since its domain is, and it is countably infinite: the terms can be laid out in a list indexed by $0, 1, 2, \ldots$ with no term left out.

Definition 2.24 (Countably infinite).

A set $T$ is countably infinite if there is a bijection $\mathbb{N}_0 \to T$ , and we then write $\#T = \#\mathbb{N}_0$ .

Removing finitely many elements from $\mathbb{N}_0$ leaves a countably infinite set, so the index set of a sequence need not be $\mathbb{N}_0$ itself; any countably infinite set of indices will do, and the terms can then be listed in the order that a bijection with $\mathbb{N}_0$ supplies.

Example 2.25 (Indexing by another set).

The even numbers $E = \{0, 2, 4, \ldots\}$ are countably infinite, since $n \mapsto 2n$ is a bijection $\mathbb{N}_0 \to E$ . So $\{a_k\}_{k \in E}$ is a sequence, with terms $a_0, a_2, a_4, \ldots$ listed in that order.

A formula may exclude some indices of its own accord. For

a_n = \frac{n}{(n-2)(n-5)}

the denominator vanishes at $n = 2$ and $n = 5$ , so the sequence is the function $f : \mathbb{N} \setminus \{2, 5\} \to \mathbb{R}$ , and its index set is again countably infinite.

Definition 2.26 (Finite sequence).

A finite sequence of elements of $A$ is a function $f : K \to A$ with $K$ finite. When $K$ is a non-empty set of natural numbers we take $K = \{1, 2, \ldots, n\}$ and call $n$ the length, writing $f = \{a_k\}_{k=1,\ldots,n}$ . For $K = \emptyset$ the function is empty and $f$ is the empty sequence, written $\varepsilon$ .

Sigma Notation

Definition 2.27 (Finite sum).

Let $\{a_k\}$ be a sequence of real numbers. For $n \in \mathbb{N}$ we write

\sum_{k=1}^{n} a_k = a_1 + a_2 + \cdots + a_n .

Each $a_k$ appearing is a term, the expression $a_k$ after the $\textstyle\sum$ is the summand, and $k$ is the index of summation, which is bound to the $\textstyle\sum$ and has no meaning outside it.

The notation says: include exactly those terms $a_k$ whose index is an integer between the lower and upper limits, inclusive. That reading has a delimited form and a general form, and the two are interchangeable:

\sum_{k=1}^{n} a_k \;=\; \sum_{1 \leqslant k \leqslant n} a_k \;=\; \sum_{k \in \{1, \ldots, n\}} a_k \;=\; \sum_{K} a_k \quad\text{for } K = \{1, \ldots, n\}.

More generally, one or more conditions written under the $\textstyle\sum$ specify which indices take part. The sum of the squares of the odd positive integers below $100$ is

\sum_{\substack{1 \leqslant k < 100 \\ k \text{ odd}}} k^2 ,

whose delimited form $\sum_{k=0}^{49}(2k+1)^2$ is harder to read; and the sum of the reciprocals of the primes up to $N$ is

\sum_{\substack{p \leqslant N \\ p \text{ prime}}} \frac{1}{p} ,

whose delimited form needs a function counting the primes before it can even be written down.

The general form also survives a change of index more transparently. Replacing $k$ by $k+1$ turns

\sum_{1 \leqslant k \leqslant n} a_k \qquad\text{into}\qquad \sum_{1 \leqslant k+1 \leqslant n} a_{k+1} ,

where the substitution can be made without thought, while in delimited form the same change reads

\sum_{k=1}^{n} a_k = \sum_{k=0}^{n-1} a_{k+1} ,

and the limits have to be recomputed by hand.

Definition 2.28 (Summation over a property).

Let $P(k)$ be a statement about integers which is true or false for each $k$ , and suppose only finitely many $k$ with $P(k)$ true have $a_k \neq 0$ . Then

\sum_{P(k)} a_k = \sum_{k \in K} a_k = \sum_{K} a_k, \qquad K = \{\, k \in \mathbb{Z} \mid P(k) \,\} .

If $P(k)$ is false for every $k$ the sum is empty, and its value is $0$ .

Example 2.29 (Reading a condition).

Let $P(n)$ be the property ” $1 \leqslant n < 100$ and $n$ is odd”. Then

K = \{\, n \in \mathbb{N} \mid P(n) \,\} = \{1, 3, 5, \ldots, 99\} = \{\, 2j+1 \mid 0 \leqslant j \leqslant 49 \,\},

\sum_{P(n)} a_n = \sum_{K} a_k = \sum_{j=0}^{49} a_{2j+1} = a_1 + a_3 + \cdots + a_{99} .

Dropping the parity condition gives $K = \{1, 2, \ldots, 99\}$ and $\sum_{P(n)}a_n = \sum_{k=1}^{99}a_k$ . Taking the summand to be $a_n = (2n+1)^2$ instead gives

\sum_{1 \leqslant n < 100} (2n+1)^2 = 3^2 + 5^2 + \cdots + 199^2 .

Remark (Keeping limits simple).

Terms equal to zero do no harm, and excluding them usually costs more than it saves. In

\sum_{k=0}^{n} k(k-1)(n-k)

the terms at $k = 0$ , $k = 1$ and $k = n$ all vanish, and one is tempted to write $\sum_{k=2}^{n-1}$ instead. That form is worse: it is harder to manipulate, and its meaning is unclear when $n = 0$ or $n = 1$ . Simple limits are worth more than a short list of terms.

Remark (Two conventions for empty sums).

An empty sum is $0$ , which fixes the value of $\sum_{k=a}^{b}a_k$ when $b < a$ :

\sum_{k=a}^{b} a_k = 0 \qquad \text{whenever } b < a .

In particular $\sum_{k=1}^{0}a_k = 0$ and $\sum_{k=0}^{-1}a_k = 0$ . With this convention the splitting rules hold without exception: for every $n \in \mathbb{N}_0$ ,

\sum_{k=1}^{n+1} a_k = \sum_{k=1}^{n} a_k + a_{n+1}, \qquad \sum_{k=0}^{n} a_k = \sum_{k=0}^{n-1} a_k + a_n ,

the second reading correctly at $n = 0$ as $a_0 = 0 + a_0$ .

Iverson Brackets

Kenneth Iverson introduced a device that removes conditions from beneath the $\textstyle\sum$ altogether.

Definition 2.30 (Iverson bracket).

For a statement $P$ that is either true or false, write

[P] = \begin{cases} 1 & \text{if } P \text{ is true}, \\ 0 & \text{if } P \text{ is false}. \end{cases}

A term multiplied by a bracket that evaluates to $0$ is taken to be $0$ even when the other factor is undefined.

With brackets, a sum over a condition becomes a sum over all integers,

\sum_{P(k)} a_k = \sum_{k} a_k\,[P(k)] ,

since the terms failing $P$ contribute nothing. The index may then be manipulated freely, with no boundary conditions to fuss over. The reciprocals of the primes up to $N$ become

\sum_{p} \frac{[\,p \text{ prime}\,]\,[\,p \leqslant N\,]}{p} ,

and the term at $p = 0$ is $0$ rather than a division by zero, by the convention in the definition.

Proposition 2.31 (Laws of summation).

Let $K$ be a finite set of integers, let $\{a_k\}$ and $\{b_k\}$ be sequences of reals, and let $c \in \mathbb{R}$ . Then

$\displaystyle \sum_{k \in K} c\,a_k = c \sum_{k \in K} a_k$ ;
$\displaystyle \sum_{k \in K} (a_k + b_k) = \sum_{k \in K} a_k + \sum_{k \in K} b_k$ ;
$\displaystyle \sum_{k \in K} a_k = \sum_{k \in K} a_{\sigma(k)}$ for every bijection $\sigma : K \to K$ .

Discussion.

Each law is a property of addition of reals lifted to a finite list of terms, so each is proved by induction on the size of $K$ , peeling off one element at a time. The first is distributivity, the second is associativity and commutativity used together to interleave two lists, and the third is commutativity alone: reordering the terms of a finite sum does not change it, and a bijection of the index set with itself is exactly a reordering. The third is the one that needs the index set to be finite, since rearranging infinitely many terms can change a sum.

Proof.

We induct on $\#K$ . If $K = \emptyset$ all three sums are empty and every claim reads $0 = 0$ .

Let $K$ be non-empty, pick $j \in K$ and write $K' = K \setminus \{j\}$ , so that $\sum_{k \in K}x_k = x_j + \sum_{k \in K'}x_k$ for any sequence $x$ .

For the first law, $\sum_{k\in K}ca_k = ca_j + \sum_{k \in K'}ca_k = ca_j + c\sum_{k\in K'}a_k = c\bigl(a_j + \sum_{k\in K'}a_k\bigr)$ , using the inductive hypothesis and then distributivity in $\mathbb{R}$ .

For the second, $\sum_{k\in K}(a_k+b_k) = (a_j+b_j) + \sum_{k\in K'}a_k + \sum_{k\in K'}b_k$ by the hypothesis, and regrouping the four terms by commutativity and associativity gives $\bigl(a_j + \sum_{k\in K'}a_k\bigr) + \bigl(b_j + \sum_{k\in K'}b_k\bigr)$ .

For the third, let $\sigma : K \to K$ be a bijection and let $j \in K$ be arbitrary. Then $\sigma$ restricts to a bijection $K \setminus \{\sigma^{-1}(j)\} \to K'$ , and splitting both sums so that the term $a_j$ is taken first reduces the claim to the same statement on a set with one fewer element.

The laws above all concern a single index set. Two different index sets combine as well.

Proposition 2.32 (Combining index sets).

Let $K$ and $K'$ be finite sets of integers. Then

\sum_{k \in K} a_k + \sum_{k \in K'} a_k = \sum_{k \in K \cap K'} a_k + \sum_{k \in K \cup K'} a_k .

Discussion.

Counting elements suggests the shape of the answer, since $\#K + \#K' = \#(K \cup K') + \#(K \cap K')$ : an element of both sets is counted twice on each side. Iverson brackets turn that count into a proof, because they replace membership by a number that can be added. The identity to establish is then $[k \in K] + [k \in K'] = [k \in K \cap K'] + [k \in K \cup K']$ for each single $k$ , which is checked by looking at the four possible cases; summing it over all $k$ and using the law for sums of sequences gives the claim.

Proof.

Fix an integer $k$ and compare the two sides of

[k \in K] + [k \in K'] = [k \in K \cap K'] + [k \in K \cup K'] .

If $k$ lies in both sets, both sides are $2$ . If it lies in exactly one, both sides are $1$ , the right-hand side because the intersection bracket is $0$ and the union bracket is $1$ . If it lies in neither, both sides are $0$ .

Multiplying by $a_k$ and summing over all integers $k$ , the second law of summation gives

\sum_k a_k[k \in K] + \sum_k a_k[k \in K'] = \sum_k a_k[k \in K \cap K'] + \sum_k a_k[k \in K \cup K'],

and each of the four sums is the corresponding sum over its index set.

Problem 2.18.

Show that $[P]\,[Q] = [P \wedge Q]$ and $[P] + [Q] - [P]\,[Q] = [P \vee Q]$ for all statements $P$ and $Q$ , and use the first of these to write

\sum_{\substack{1 \leqslant k \leqslant n \\ k \text{ odd}}} a_k

as a sum over all integers $k$ with no condition beneath the sign.

Geometric Sums

Definition 2.33 (Geometric sequence).

A sequence $\{a_n\}$ of reals is geometric with ratio $q$ if $a_{n+1} = q\,a_n$ for every $n \in \mathbb{N}_0$ , equivalently if $a_n = a_0 q^n$ for every $n$ .

Proposition 2.34 (Geometric sum).

Let $q \neq 1$ and $n \in \mathbb{N}_0$ . Then

\sum_{k=0}^{n} a_0 q^k = a_0\,\frac{1 - q^{\,n+1}}{1 - q} .

Discussion.

Multiplying the sum by $q$ shifts every term one place along, so the product and the original share all their terms but two: the original has $a_0$ where the product has nothing, and the product has $a_0q^{n+1}$ where the original has nothing. Subtracting therefore cancels everything in the middle and leaves those two terms, which is a linear equation for the sum. The hypothesis $q \neq 1$ is what allows the division at the end, and it is needed: at $q = 1$ every term is $a_0$ and the sum is $(n+1)a_0$ .

Proof.

Write $S = \sum_{k=0}^{n}a_0q^k = a_0 + a_0q + \cdots + a_0q^n$ . By the first law of summation,

qS = a_0q + a_0q^2 + \cdots + a_0q^{n} + a_0q^{\,n+1} .

Every term of $qS$ with exponent between $1$ and $n$ appears in $S$ as well, so subtracting leaves only the extremes:

S - qS = a_0 - a_0 q^{\,n+1}, \qquad\text{that is}\qquad S(1 - q) = a_0\bigl(1 - q^{\,n+1}\bigr).

Since $q \neq 1$ we may divide by $1 - q$ .

Example 2.35 (Halving).

With $a_0 = 1$ and $q = \tfrac12$ ,

\sum_{k=0}^{n} \left(\tfrac{1}{2}\right)^{k} = \frac{1 - (1/2)^{n+1}}{1 - 1/2} = 2 - \left(\tfrac{1}{2}\right)^{n}.

Starting the sum at $k = 1$ removes the term $1$ , so

\sum_{k=1}^{n} \left(\tfrac{1}{2}\right)^{k} = 1 - \left(\tfrac{1}{2}\right)^{n},

which is what one expects: halving repeatedly closes all but the last gap.

Sums and Recurrences

Writing $S_n = \sum_{k=0}^{n} a_k$ and splitting off the last term gives $S_n = S_{n-1} + a_n$ , so a sum is a recurrence and the methods of the previous chapter apply to it. The correspondence runs both ways, and this section uses it in each direction.

Proposition 2.36 (A sum is a recurrence).

Let $\{a_k\}$ be a sequence of reals and put $S_n = \sum_{k=0}^{n}a_k$ . Then $S$ is the unique function $\mathbb{N}_0 \to \mathbb{R}$ with

S_0 = a_0, \qquad S_n = S_{n-1} + a_n \quad (n \geqslant 1),

and conversely any function satisfying those two conditions is given by that sum.

Discussion.

Both halves come from the splitting rule for sums, which is where the convention that an empty sum is $0$ earns its place: it makes $S_0$ come out as $a_0$ with no separate argument. For the forward direction, split the last term off the sum defining $S_n$ . For the converse, the two conditions determine the value at every $n$ from the value below it, so at most one function satisfies them, and the sum has just been shown to be one.

Proof.

At $n = 0$ the sum has the single term $a_0$ , so $S_0 = a_0$ . For $n \geqslant 1$ , splitting off the term at $k = n$ gives

S_n = \sum_{k=0}^{n} a_k = \sum_{k=0}^{n-1}a_k + a_n = S_{n-1} + a_n .

Conversely, suppose $R : \mathbb{N}_0 \to \mathbb{R}$ satisfies $R_0 = a_0$ and $R_n = R_{n-1} + a_n$ for $n \geqslant 1$ . Then $R_0 = S_0$ , and if $R_{n-1} = S_{n-1}$ then $R_n = R_{n-1} + a_n = S_{n-1} + a_n = S_n$ . By induction $R = S$ .

Used from left to right, this turns a sum into a recurrence to be solved by the techniques already available. The repertoire method of the previous chapter applies without change, and the recurrence to feed it is the general first-order one with a linear term.

Theorem 2.37 (A linear sum-recurrence).

Let $\alpha, \beta, \gamma \in \mathbb{R}$ and let $R$ satisfy

R_0 = \alpha, \qquad R_n = R_{n-1} + \beta + \gamma n \quad (n \geqslant 1).

Then

R_n = \alpha + \beta n + \gamma\,\frac{n^2 + n}{2} .

Discussion.

Computing $R_1 = \alpha + \beta + \gamma$ , $R_2 = \alpha + 2\beta + 3\gamma$ and $R_3 = \alpha + 3\beta + 6\gamma$ shows every value to be a combination $A(n)\alpha + B(n)\beta + C(n)\gamma$ whose coefficients do not depend on the three constants, so the repertoire method applies: choose functions $R$ that satisfy the recurrence for some values of $\alpha, \beta, \gamma$ , and read off one equation in $A$ , $B$ , $C$ from each. The constant function $1$ forces $\beta = \gamma = 0$ and gives $A$ outright; the function $n$ forces $\beta = 1$ , $\gamma = 0$ and gives $B$ ; and the function $n^2$ forces $\beta = -1$ , $\gamma = 2$ , which involves $B$ and $C$ together and so needs the previous two results to finish. Three substitutions give three equations, and the system is triangular.

Proof.

Write $R_n = A(n)\alpha + B(n)\beta + C(n)\gamma$ , which the first few values show to be the right shape, and determine the coefficients by substitution. Each substitution takes a function $R$ , asks which $\alpha, \beta, \gamma$ make it satisfy the recurrence, and then reads the displayed identity at those values.

Take $R_n = 1$ . Then $R_0 = 1$ forces $\alpha = 1$ , and the recurrence reads $1 = 1 + \beta + \gamma n$ , that is $\beta + \gamma n = 0$ for every $n$ , which forces $\beta = \gamma = 0$ . Substituting $(\alpha, \beta, \gamma) = (1, 0, 0)$ gives

1 = A(n) .

Take $R_n = n$ . Then $R_0 = 0$ forces $\alpha = 0$ , and the recurrence reads $n = (n-1) + \beta + \gamma n$ , that is $1 = \beta + \gamma n$ for every $n$ , which forces $\beta = 1$ and $\gamma = 0$ . Substituting $(0, 1, 0)$ gives

n = B(n) .

Take $R_n = n^2$ . Then $\alpha = 0$ , and the recurrence reads $n^2 = (n-1)^2 + \beta + \gamma n$ , that is

0 = -2n + 1 + \beta + \gamma n = (1 + \beta) + (\gamma - 2)n

for every $n$ , which forces $\beta = -1$ and $\gamma = 2$ . Substituting $(0, -1, 2)$ gives

n^2 = -B(n) + 2C(n) = -n + 2C(n), \qquad\text{so}\qquad C(n) = \frac{n^2+n}{2}.

Assembling, $R_n = \alpha + \beta n + \gamma(n^2+n)/2$ . Finally this function does satisfy the recurrence, as substituting it into $R_{n-1} + \beta + \gamma n$ confirms, and the recurrence with its boundary condition has only one solution.

Example 2.38 (Summing an arithmetic progression).

Let $a, b \in \mathbb{R}$ and $S_n = \sum_{k=0}^{n}(a + bk)$ . By the correspondence above, $S_0 = a$ and $S_n = S_{n-1} + (a + bn)$ , which is the recurrence of the theorem with $\alpha = a$ , $\beta = a$ and $\gamma = b$ . Hence

\sum_{k=0}^{n}(a + bk) = a + na + \frac{n^2+n}{2}b = (n+1)a + \frac{n(n+1)}{2}b .

The same answer comes out of the summation laws directly: splitting the summand and pulling out the constants,

\sum_{k=0}^{n}(a + bk) = \sum_{k=0}^{n}a + b\sum_{k=0}^{n}k = (n+1)a + b\,\frac{n(n+1)}{2},

since a sum of $n+1$ copies of $a$ is $(n+1)a$ . The repertoire method earns its keep on recurrences that are not sums of anything recognisable.

The Summation Factor

Used from right to left, the correspondence turns a recurrence into a sum. A recurrence of the form $S_n = S_{n-1} + c_n$ is immediately a sum, so the problem is to bring a given recurrence into that shape, and multiplying through by a well-chosen factor does it.

Theorem 2.39 (Summation factor).

Let $\{a_n\}$ , $\{b_n\}$ , $\{c_n\}$ be sequences of reals with $a_n \neq 0$ and $b_n \neq 0$ for every $n \geqslant 1$ , and let $T$ satisfy

a_n T_n = b_n T_{n-1} + c_n \qquad (n \geqslant 1),

with $T_0$ given. Put $s_1 = 1$ and

s_n = \frac{a_1 a_2 \cdots a_{n-1}}{b_2 b_3 \cdots b_n} \qquad (n \geqslant 2).

Then $s_n b_n = s_{n-1}a_{n-1}$ for every $n \geqslant 2$ , and

T_n = \frac{1}{s_n a_n}\left( s_1 b_1 T_0 + \sum_{k=1}^{n} s_k c_k \right) \qquad (n \geqslant 1).

Discussion.

The obstruction to reading the recurrence as a sum is that $T_n$ and $T_{n-1}$ carry different coefficients. Multiplying the whole equation by a factor $s_n$ removes the obstruction provided the new coefficient of $T_{n-1}$ , namely $s_nb_n$ , equals the coefficient that $T_{n-1}$ had at the previous step, namely $s_{n-1}a_{n-1}$ ; that condition is a recurrence for $s_n$ itself, and unrolling it gives the stated product. With the factor in hand, $S_n = s_na_nT_n$ satisfies $S_n = S_{n-1} + s_nc_n$ , which the previous proposition evaluates as a sum. Dividing by $s_na_n$ at the end is legitimate because both factors are non-zero, which is exactly what the hypotheses on $a_n$ and $b_n$ guarantee.

Proof.

For $n \geqslant 2$ , the definition of $s_n$ gives

s_n b_n = \frac{a_1 \cdots a_{n-1}}{b_2 \cdots b_n}\,b_n = \frac{a_1 \cdots a_{n-1}}{b_2 \cdots b_{n-1}} = \frac{a_1 \cdots a_{n-2}}{b_2\cdots b_{n-1}}\,a_{n-1} = s_{n-1}a_{n-1},

with the case $n = 2$ reading $s_2b_2 = a_1 = s_1a_1$ .

Multiply the recurrence by $s_n$ and set $S_n = s_na_nT_n$ . For $n \geqslant 2$ ,

S_n = s_na_nT_n = s_nb_nT_{n-1} + s_nc_n = s_{n-1}a_{n-1}T_{n-1} + s_nc_n = S_{n-1} + s_nc_n,

and at $n = 1$ the recurrence gives $S_1 = s_1a_1T_1 = s_1(b_1T_0 + c_1) = s_1b_1T_0 + s_1c_1$ . So $S$ satisfies a sum-recurrence started at $s_1b_1T_0$ , and unrolling it gives

S_n = s_1b_1T_0 + \sum_{k=1}^{n}s_kc_k .

Since $s_n \neq 0$ and $a_n \neq 0$ , dividing $S_n = s_na_nT_n$ by $s_na_n$ gives the stated formula.

Example 2.40 (The Tower of Hanoi again).

The recurrence $T_n = 2T_{n-1} + 1$ has $a_n = 1$ , $b_n = 2$ and $c_n = 1$ , so a summation factor is $s_n = 2^{-n}$ , which satisfies $s_nb_n = 2^{-(n-1)} = s_{n-1}a_{n-1}$ . Multiplying through,

\frac{T_n}{2^n} = \frac{T_{n-1}}{2^{\,n-1}} + \frac{1}{2^n},

so $S_n = T_n/2^n$ obeys $S_0 = 0$ and $S_n = S_{n-1} + 2^{-n}$ . That is a geometric sum,

S_n = \sum_{k=1}^{n}\frac{1}{2^k} = 1 - \frac{1}{2^n},

and multiplying back by $2^n$ gives $T_n = 2^n - 1$ .

Remark (Where the factor comes from).

The condition $s_nb_n = s_{n-1}a_{n-1}$ is itself a recurrence, $s_n = s_{n-1}a_{n-1}/b_n$ , and unrolling it from $s_1 = 1$ produces the product in the theorem. Any non-zero constant multiple of that product serves equally well, since multiplying every $s_n$ by the same constant leaves the condition and the final formula unchanged; in the Hanoi example the product gives $2^{-(n-1)}$ and we used $2^{-n}$ . The method needs every $a_n$ and every $b_n$ to be non-zero, and fails otherwise.

Definition 2.41 (Harmonic numbers).

For $n \in \mathbb{N}_0$ the $n$ th harmonic number is

H_n = \sum_{k=1}^{n}\frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n},

so that $H_0 = 0$ . The name comes from music: the $k$ th harmonic of a vibrating string is the tone produced by a string $1/k$ times as long.

Harmonic numbers have no closed form in the sense of this chapter, and they are what a summation factor produces as soon as the coefficients of a recurrence vary with $n$ .

Example 2.42 (A recurrence with variable coefficients).

The Hanoi recurrence had constant $a_n$ and $b_n$ , so the factor was a constant power. Consider instead

T_0 = 0, \qquad n\,T_n = (n+1)\,T_{n-1} + 2n \qquad (n \geqslant 1),

with $a_n = n$ , $b_n = n+1$ and $c_n = 2n$ . The summation factor is

s_n = \frac{a_1 a_2 \cdots a_{n-1}}{b_2 b_3 \cdots b_n} = \frac{(n-1)!}{(n+1)!/2} = \frac{2}{n(n+1)} ,

which agrees with $s_1 = 1$ . Then $s_n a_n T_n = 2T_n/(n+1)$ and $s_k c_k = 4/(k+1)$ , while $s_1 b_1 T_0 = 0$ , so the theorem gives

\frac{2T_n}{n+1} = \sum_{k=1}^{n}\frac{4}{k+1}, \qquad\text{that is}\qquad T_n = 2(n+1)\sum_{k=1}^{n}\frac{1}{k+1} .

The remaining sum is a harmonic number in disguise. Shifting the index by one,

\sum_{k=1}^{n}\frac{1}{k+1} = \sum_{2 \leqslant k \leqslant n+1}\frac{1}{k} = \sum_{1 \leqslant k \leqslant n}\frac{1}{k} - 1 + \frac{1}{n+1} = H_n - \frac{n}{n+1},

where the middle step dropped the term at $k = 1$ and added the one at $k = n+1$ . Therefore

T_n = 2(n+1)\left(H_n - \frac{n}{n+1}\right) = 2(n+1)H_n - 2n ,

and checking at $n = 1$ gives $T_1 = 4H_1 - 2 = 2$ , which the recurrence confirms.

Problem 2.19.

Use a summation factor to solve $T_0 = 1$ and $nT_n = (n+1)T_{n-1} + n(n+1)$ for $n \geqslant 1$ .

Problem 2.20.

Prove that $H_{2n} - H_n \geqslant \tfrac{1}{2}$ for every $n \in \mathbb{N}$ , and deduce that $H_n$ can be made as large as we please by taking $n$ large enough.

Exercises on Recurrences

Exercise 2.1.

Compute $T_n$ for the Tower of Hanoi for $n = 1, \ldots, 8$ from the recurrence, and check each against $2^n - 1$ .

Exercise 2.2.

Suppose a fourth peg is added to the Tower of Hanoi. Give a strategy for $n$ discs using the extra peg, count its moves, and compare the count with $2^n - 1$ for $n = 4, 8, 16$ .

Exercise 2.3.

Solve each recurrence by unrolling, then confirm the answer by induction.

$f(0) = 2$ and $f(n) = 3f(n-1)$ for $n \geqslant 1$ ;
$f(0) = 0$ and $f(n) = f(n-1) + 2n - 1$ for $n \geqslant 1$ ;
$f(1) = 1$ and $f(n) = f(n-1) + 1/n$ for $n \geqslant 2$ , as far as a sum in closed form allows.

Exercise 2.4.

Solve $f(0) = 1$ , $f(n) = 3f(n-1) + 4$ for $n \geqslant 1$ by the substitution $U_n = f(n) + c$ , choosing $c$ so that the recurrence for $U_n$ has no constant term.

Exercise 2.5.

What is the largest number of regions into which $n$ circles can cut the plane? Find the recurrence and solve it.

Exercise 2.6.

What is the largest number of pieces into which $n$ planes can cut three-dimensional space? Argue that the answer satisfies $P_n = P_{n-1} + L_{n-1}$ , where $L_n$ is the count for lines in the plane, and solve.

Exercise 2.7.

For each recurrence, write down the characteristic equation, find its roots, and give the solution meeting the stated boundary conditions.

$f(0) = 0$ , $f(1) = 1$ , $f(n) = 6f(n-1) - 8f(n-2)$ ;
$f(0) = 1$ , $f(1) = 2$ , $f(n) = 2f(n-1) - f(n-2)$ ;
$f(0) = 1$ , $f(1) = 0$ , $f(2) = 1$ , $f(n) = 3f(n-2) - 2f(n-3)$ .

Exercise 2.8.

Solve $f(0) = 0$ and $f(n) = 2f(n-1) + n^2$ for $n \geqslant 1$ .

Exercise 2.9.

Let $f$ satisfy the Fibonacci recurrence with $f(0) = f(1) = 1$ . Prove that $f(0) + f(1) + \cdots + f(n) = f(n+2) - 1$ .

Exercise 2.10.

Compute $J(n)$ for $n = 17, \ldots, 32$ and check that the values run through the odd numbers below $32$ and then restart at $1$ .

Exercise 2.11.

Suppose the circle is counted in the other direction, so that the first person eliminated is the one before the leader rather than after. Work out the survivor for $n = 1, \ldots, 8$ and find a recurrence.

Exercise 2.12.

Use the repertoire method on $f(1) = \alpha$ , $f(2\ell) = 2f(\ell) + \beta\ell$ , $f(2\ell+1) = 2f(\ell) + \gamma\ell$ , taking $f(n) = 1$ and $f(n) = n$ as two of the substitutions.

Exercise 2.13.

Convert $2026$ to base $2$ , base $3$ and base $16$ , and check each answer by Horner’s scheme.

Exercise 2.14.

Let $b > 1$ and $z \in \mathbb{N}$ . Show that $z$ and $z+1$ have the same number of base- $b$ digits unless $z + 1$ is a power of $b$ , and use this to count how many numbers have exactly $n$ digits in base $b$ .

Exercise 2.15.

Show that $\lfloor x \rfloor + \lceil x \rceil = 2\lfloor x \rfloor$ when $x \in \mathbb{Z}$ and $2\lfloor x \rfloor + 1$ otherwise, and that $\lfloor x + k \rfloor = \lfloor x \rfloor + k$ for every $k \in \mathbb{Z}$ .

Exercises on Sums

Exercise 2.16.

Some of the regions cut out by $n$ lines in the plane are bounded and the rest are not. What is the largest possible number of bounded regions?

Exercise 2.17.

Let $H(n) = J(n+1) - J(n)$ , with $J$ the Josephus survivor. The recurrence for $J$ gives $H(2n) = 2$ and

H(2n+1) = J(2n+2) - J(2n+1) = \bigl(2J(n+1) - 1\bigr) - \bigl(2J(n) + 1\bigr) = 2H(n) - 2

for every $n \geqslant 1$ . It therefore looks possible to prove $H(n) = 2$ for all $n$ by induction. Compute $H(1)$ , $H(2)$ and $H(3)$ , and say exactly what is wrong with the argument.

Exercise 2.18.

Let $\alpha, \beta \in \mathbb{R}$ and define $Q_0 = \alpha$ , $Q_1 = \beta$ and

Q_n = \frac{1 + Q_{n-1}}{Q_{n-2}} \qquad (n \geqslant 2),

assuming $\alpha$ and $\beta$ are such that no denominator ever vanishes. Compute $Q_2, \ldots, Q_6$ and prove that $Q_{n+5} = Q_n$ for every $n \in \mathbb{N}_0$ .

Exercise 2.19.

Evaluate

\sum_{k} \,[\,1 \leqslant j \leqslant k \leqslant n\,]

as a function of $j$ and $n$ , taking care over the values of $j$ for which the sum is empty.

Exercise 2.20.

Prove the rule for summation by parts: for every $n \in \mathbb{N}_0$ ,

\sum_{0 \leqslant k < n} (a_{k+1} - a_k)\,b_k = a_n b_n - a_0 b_0 - \sum_{0 \leqslant k < n} a_{k+1}\,(b_{k+1} - b_k) .

Use only the distributive, associative and commutative laws of summation together with a shift of the index.

Exercise 2.21.

Find a closed form for

\sum_{k=0}^{n} (-1)^k k^2 .

Exercise 2.22.

Use a summation factor to solve

T_0 = 5, \qquad 2T_n = n\,T_{n-1} + 3 \cdot n! \quad (n \geqslant 1),

and check your answer at $n = 1$ and $n = 2$ .

Exercise 2.23.

Evaluate $\sum_{k=0}^{n} k\,2^k$ by writing the recurrence it satisfies and solving it, and check the answer for $n \leqslant 4$ .

Exercise 2.24.

Show that $\sum_{k=1}^{n} \dfrac{1}{k(k+1)} = 1 - \dfrac{1}{n+1}$ , first by unrolling the corresponding recurrence and then by writing $\dfrac{1}{k(k+1)} = \dfrac{1}{k} - \dfrac{1}{k+1}$ and cancelling.

Exercise 2.25.

Let $K$ and $K'$ be finite sets of integers with $K \cap K' = \emptyset$ . Deduce from the law for combining index sets that $\sum_{k \in K \cup K'}a_k = \sum_{k \in K}a_k + \sum_{k \in K'}a_k$ , and give an example showing the hypothesis is needed.

Exercise 2.26.

Write each of the following as a sum with the index running from $0$ , using Iverson brackets where a condition is needed.

$\displaystyle\sum_{\substack{1 \leqslant k \leqslant 100 \\ k \text{ divisible by } 3}} k$ ;
$\displaystyle\sum_{k=5}^{20} \frac{1}{k-4}$ ;
the sum of $a_k$ over those $k$ between $1$ and $n$ that are perfect squares.

Check Yourself

Fresh questions on the whole chapter — none of them is worked out above. Do each on paper first; the box only tells you whether you got there.

Answers are checked in your browser, as often as you like. Nothing is sent anywhere and nothing is kept but your own work. A formula may be written with the symbols themselves or with ~ & | -> <-> ^, and \and, \or, \to expand as you type.