5.1 Sequences, recursion, and series

What a sequence really is

A sequence is not merely a row of numbers written with commas. Formally, it is a function whose input is a positive integer and whose output is a real number. The input tells us the position of the term. The output is the value sitting at that position.

Definition

Sequence of real numbers

A sequence of real numbers is a function

$$a:\mathbb Z^+\to \mathbb R.$$

Instead of writing $a(n)$, we usually write $a_n$, and we denote the whole sequence by $\{a_n\}$. Here the starting index is $n=1$, and all general-term formulas in this definition apply for integers $n ≥ 1$.

This definition is worth taking seriously. It explains why the same values in a different order form a different sequence, and why a formula for $a_n$ must say what happens for every positive integer $n$.

Worked example

Reading a general term

If $a_n=(-1)^n$, then

$$a_1=-1,\quad a_2=1,\quad a_3=-1,\quad a_4=1.$$

If $b_n=2^{n-1}$, then

$$b_1=1,\quad b_2=2,\quad b_3=4,\quad b_4=8.$$

Both are sequences because each positive integer $n$ determines exactly one real number.

Checkpoint

A sequence is formally a function from which set to which set in this chapter?

Use the chapter definition.

Solution · Answer

It is a function $a:\mathbb Z^+\to\mathbb R$, so each positive integer index returns one real-number term.

Finding general terms from patterns

A finite list suggests a pattern, but the general term must describe the $n$-th term, not just the first few terms. Without a rule, a finite initial list never uniquely determines an infinite sequence: a later term can be changed while every listed term stays the same. In pattern exercises, the intended continuation must therefore be stated as part of the proposed rule.

Worked example

Alternating zeros and ones

The sequence

$$1,0,1,0,\ldots$$

is $1$ when $n$ is odd and $0$ when $n$ is even. A compact formula is

$$a_n=\frac{1+(-1)^{n-1}}2.$$

When $n$ is odd, $n-1$ is even and the numerator is $2$. When $n$ is even, $n-1$ is odd and the numerator is $0$.

Worked example

Products of even and odd factors

The product

$$2\cdot4\cdot6\cdots(2n)$$

has the $k$-th factor $2k$. Therefore

$$2\cdot4\cdots(2n) =\prod_{k=1}^n 2k =2^n n!.$$

Similarly,

$$1\cdot3\cdot5\cdots(2n-1) =\frac{(2n)!}{2^n n!},$$

because $(2n)!$ is the product of all factors from $1$ to $2n$, and dividing by the even part $2\cdot4\cdots(2n)=2^n n!$ leaves only the odd part.

Worked example

A sequence made from repeated differentiation

The chapter also uses $f(x)=\sin x$ to show that sequences do not have to come from ordinary lists first. Define $a_n=f^{(n)}(0)$, where $f^{(n)}$ means the $n$-th derivative. The derivatives cycle:

$$\sin x,\quad \cos x,\quad -\sin x,\quad -\cos x,\quad \sin x,\ldots$$

So

$$a_1=1,\quad a_2=0,\quad a_3=-1,\quad a_4=0,$$

and the same four-term pattern repeats. One compact general term is

$$a_n=\cos\left(\frac{(n-1)\pi}{2}\right).$$

This example is important because it separates the idea of a sequence from the idea of a simple algebraic pattern. The sequence is still a function of the index $n$; its values are produced by a calculus operation before evaluating at $0$.

Common mistake

A pattern is not a definition until the indexing is fixed

With indexing starting at $n=1$, the formula $a_n=2^n$ gives $2,4,8,...$, whereas $a_n=2^{n-1}$ gives $1,2,4,...$. These are different sequences, not interchangeable descriptions of the same list. Substituting the first index is a quick way to check whether a proposed formula has shifted the sequence.

Recursive definitions

Some sequences are easier to define by saying how to get the next term from earlier terms. An explicit definition computes a term directly from its index; a recursive definition specifies how known terms determine later ones. A first-order rule needs a starting value, and a rule involving the previous two terms generally needs two starting values. The rule alone does not choose those values. A recurrence with sufficient initial data can define a sequence completely even when no convenient closed formula is available.

Definition

Recursive sequence

A recursive sequence is a sequence whose terms are defined using one or more preceding terms, together with enough initial values to start the process.

For example,

$$a_1=4,\qquad a_{n+1}=2a_n+1$$

gives

$$a_2=9,\quad a_3=19,\quad a_4=39.$$

The recurrence determines the next term only after the earlier term is known.

For this particular recurrence, we can also find a closed formula. Add $1$ to both sides and set $b_n=a_n+1$. Then

$$b_{n+1}=a_{n+1}+1=2a_n+2=2(a_n+1)=2b_n.$$

Since $b_1=a_1+1=5$, the transformed sequence is geometric:

$$b_n=5\cdot2^{n-1}.$$

Therefore

$$a_n=b_n-1=5\cdot2^{n-1}-1.$$

The lesson is not that every recurrence becomes geometric. The useful habit is to look for a change of variables that removes the constant term when the recurrence is affine.

Concept lensAlgorithmic

One sequence, two ways to obtain a term

The explicit formula $a_n=5\cdot2^{n-1}-1$ takes a positive integer $n$ as its input. To obtain $a_4$, substitute $n=4$ and get $39$ directly. The recursive description instead starts from $a_1=4$ and repeatedly applies $x\mapsto2x+1$, generating $4,9,19,39$. It describes how to produce the next value from the current value; the initial value is part of that description.

These are two descriptions of the same sequence, not two different kinds of number. The derivation above links the step-by-step process to the explicit formula for every integer $n\ge1$. Agreement at the first four terms alone would not establish that link. Use the explicit view when asking for a term at a specified index, and the recursive view when following successive changes. The existence of a generative rule does not by itself supply a closed formula.

Theorem

Recursion theorem

Let $X$ be a set, let $b\in X$, and let $f:X\to X$ be a function. Then there is a unique function $a:\mathbb Z^+\to X$ such that

$$a(1)=b,\qquad a(n+1)=f(a(n))$$

for every $n\in\mathbb Z^+$.

The theorem gives the formal reason why a first term plus a rule such as $a_{n+1}=f(a_n)$ really defines a sequence. The rule never leaves $X$, because $f$ maps $X$ back into $X$, and uniqueness says that there is no second sequence satisfying the same starting value and same next-term rule. Existence means the repeated construction supplies a value at every positive integer index. Uniqueness can be understood step by step: two proposed sequences agree at the first term, and whenever they agree at one term, applying the same function forces agreement at the next. Requiring $f:X\to X$ is essential; the next step must remain defined after every previous step.

Worked example

Turning a recurrence into theorem data

For

$$a_1=1,\qquad a_{n+1}=a_n^2+1,$$

take $X=\mathbb R$, $b=1$, and $f(x)=x^2+1$. The recursion theorem says that there is a unique real sequence satisfying this rule. The first terms are

$$1,\quad 2,\quad 5,\quad 26,\ldots$$

There may be no simple closed formula, but the sequence is still completely defined.

Fibonacci as a first-order recursion on pairs

The Fibonacci sequence is defined by two starting values and a rule using the previous two terms:

$$F_1=F_2=1,\qquad F_{n+2}=F_{n+1}+F_n.$$

To fit the recursion theorem, package two consecutive values as one ordered pair:

$$a(n)=(F_n,F_{n+1}).$$

Then the next pair is obtained from the function

$$f(x,y)=(y,x+y).$$

So a two-term recurrence can be viewed as a one-step recurrence on the set $\mathbb R^2$. The full theorem data are $X=\mathbb R^2$, $b=(1,1)$, and $f(x,y)=(y,x+y)$. The function always returns a real pair. Its second coordinate stores the information needed for the following step; starting from $(1,1)$ gives $(1,2)$ and then $(2,3)$. Thus uniqueness applies to the pair sequence and consequently to the Fibonacci terms.

Theorem

Binet form of Fibonacci numbers

Let

$$\phi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}.$$

Then for every positive integer $n$,

$$F_n=\frac{\phi^n-\psi^n}{\phi-\psi}.$$

This formula is usually proved by checking that the right-hand side has the same first two values and satisfies the same recurrence. The essential identities are $\phi^2=\phi+1$ and $\psi^2=\psi+1$.

Here is the verification in a form that is useful for similar recurrence questions. Define

$$B_n=\frac{\phi^n-\psi^n}{\phi-\psi}.$$

The denominator is $\phi-\psi=\sqrt5\ne0$, so this defines a real number for every positive integer index. Checking the recurrence alone would not identify Fibonacci: the two initial values must also be checked.

First,

$$B_1=1,\qquad B_2=\frac{\phi^2-\psi^2}{\phi-\psi}=\phi+\psi=1.$$

Next, because each of $\phi$ and $\psi$ satisfies $t^2=t+1$, we have

$$\phi^{n+2}=\phi^{n+1}+\phi^n, \qquad \psi^{n+2}=\psi^{n+1}+\psi^n.$$

Subtracting the second identity from the first and dividing by $\phi-\psi$ gives

$$B_{n+2}=B_{n+1}+B_n.$$

Thus $\{B_n\}$ has the same first two values and the same recursive rule as the Fibonacci sequence. By uniqueness of the recursively defined sequence, $B_n$ must equal $F_n$ for every positive integer $n$.

Arithmetic sequences and sums

Definition

Arithmetic sequence

A sequence $\{a_n\}$ is arithmetic if there is a constant $d$ such that

$$a_{n+1}-a_n=d$$

for every $n\in\mathbb Z^+$. The number $d$ is the common difference.

From the first term to the $n$-th term there are $n-1$ increments, each equal to $d$. Adding the successive differences gives $a_n-a_1=(n-1)d$. Thus, if $a=a_1$, the general term is

$$a_n=a+(n-1)d.$$

The sum of the first $n$ terms is

$$s_n=\sum_{k=1}^n a_k =\frac n2\left[2a+(n-1)d\right] =\frac n2(a_1+a_n).$$

To justify pairing for both odd and even numbers of terms, write the sum forwards and backwards and add the two copies:

$$\begin{aligned} s_n&=a_1+a_2+\cdots+a_n,\\ s_n&=a_n+a_{n-1}+\cdots+a_1,\\ 2s_n&=n(a_1+a_n). \end{aligned}$$

Every column has sum $a_1+a_n$, because its two indices add to $n+1$. For even $n$, the original terms form distinct first-last pairs. For odd $n$, the middle term is half of $a_1+a_n$; in the two-copy argument it is added to itself. There are always exactly $n$ columns, so dividing by two is valid in either case.

Worked example

Recover an arithmetic sequence from a sum

Suppose the common difference is $d=3/2$ and the sum of the first $15$ terms is $240$. Then

$$240=\frac{15}{2}\left[2a+14\cdot\frac32\right].$$

Solving gives $a=5.5$.

If the sum of the first $k$ terms is $361$, then

$$\frac{k}{2}\left[2(5.5)+(k-1)\frac32\right]=361.$$

This simplifies to

$$3k^2+19k-1444=0.$$

The positive integer solution is $k=19$; the other root is rejected because a number of terms cannot be negative.

Checkpoint

What is the sum of the first $n$ terms of an arithmetic sequence with first term $a$ and common difference $d$?

Use first-last pairing.

Solution · Answer

$$s_n=\frac n2\left[2a+(n-1)d\right].$$

Geometric sequences and sums

Definition

Geometric sequence

A sequence $\{b_n\}$ of nonzero numbers is geometric if there is a nonzero constant $r$ such that

$$\frac{b_{n+1}}{b_n}=r$$

for every $n\in\mathbb Z^+$. The number $r$ is the common ratio.

If $b=b_1$, then

$$b_n=br^{n-1}.$$

For $r\ne 1$, the finite geometric sum is

$$\sum_{k=1}^n br^{k-1} =b\sum_{k=0}^{n-1}r^k =b\frac{1-r^n}{1-r} =b\frac{r^n-1}{r-1}.$$

Let $G_n=1+r+\cdots+r^{n-1}$. Multiplication by $r$ shifts every exponent up by one, giving $rG_n=r+r^2+\cdots+r^n$. On subtraction, all powers from $r$ through $r^{n-1}$ cancel. The first term of $G_n$ and the last term of $rG_n$ remain, so

$$(1-r)(1+r+\cdots+r^{n-1})=1-r^n.$$

If $r=1$, every term is $b$, so the sum is $bn$; division by $1-r$ is not allowed. These are finite sums for positive integers $n$, and the cancellation requires no assumption about infinite convergence.

Checkpoint

Why does the geometric-sum formula need a separate case when $r=1$?

Look at the denominator.

Solution · Answer

The formula $b(1-r^n)/(1-r)$ divides by $1-r$, which is zero when $r=1$. In that case every term is $b$, so the sum is $bn$.

Arithmetic-geometric sums

A useful final exercise mixes an arithmetic factor with a geometric factor. Let

$$x_k=(a+kd)br^k,\qquad k=0,1,2,\ldots,$$

where $r\ne0$ and $r\ne1$. For an integer $n ≥ 1$, define

$$S_n=\sum_{k=0}^{n-1}x_k =\sum_{k=0}^{n-1}(a+kd)br^k.$$

Use the same subtraction method, now tracking the changing coefficients. Separate the endpoints before aligning the interior powers:

$$\begin{aligned} S_n&=ab+\sum_{k=1}^{n-1}(a+kd)br^k,\\ rS_n&=\sum_{k=1}^{n-1}(a+(k-1)d)br^k +(a+(n-1)d)br^n. \end{aligned}$$

For each interior power $r^k$, the coefficient difference is $(a+kd)-(a+(k-1)d)=d$. The constant term occurs only in the first line, while the power $r^n$ occurs only in the second. Therefore

$$(1-r)S_n =ab+db\sum_{k=1}^{n-1}r^k-(a+(n-1)d)br^n.$$

To express the middle sum using the same endpoint $r^n$ as the final formula, start with $r+r^2+\cdots+r^n$ and remove its last term:

$$\sum_{k=1}^{n-1}r^k =\frac{r(1-r^n)}{1-r}-r^n.$$

Substitution contributes an extra $-dbr^n$. Combining it with the previous boundary term changes $a+(n-1)d$ into $a+nd$. Dividing by $1-r$ gives

$$S_n= \frac{ab-(a+nd)br^n}{1-r} +\frac{dbr(1-r^n)}{(1-r)^2}.$$

For $n=1$, the interior sums are empty and have value zero: the original sum is just $S_1=ab$. The two fractions above also reduce to $ab$, because the extra terms involving $d$ cancel. Setting $d=0$ instead recovers $S_n=ab(1-r^n)/(1-r)$, the ordinary geometric sum. These checks retain the first and last terms and help detect an indexing error.

Common mistake

Watch the shifted boundary term

The boundary term is the subtle point. The last term in $rS_n$ is $(a+(n-1)d)br^n$, but after combining with the finite geometric sum the equivalent final formula can be written with $(a+nd)br^n$.

Checkpoint

In the arithmetic-geometric sum, why is the method $S_n-rS_n$ useful?

Track what happens to the coefficient $a+kd$ after shifting by one power of $r$.

Solution · Answer

Most terms line up with the same power of $r$, and their coefficients differ by exactly $d$. That leaves two boundary terms and a geometric sum $db(r+\cdots+r^{n-1})$, which can be simplified by the ordinary geometric-sum formula.

An applied recurrence: the mortgage formula

The chapter's mortgage example is a useful applied recurrence. Let:

• $P\gt 0$ be the initial principal;
• $R$ be the fixed nominal annual interest rate written as a decimal;
• $N$ be a positive integer number of monthly payments;
• $x$ be the fixed payment made at the end of each month;
• $L_n$ be the outstanding balance immediately after payment $n$.

The model uses monthly rate $R/12$: interest is applied to the previous balance first, then the payment is subtracted. For example, an annual rate of $3\%$ means $R=0.03$, not $R=3$. Month zero records the principal before any interest or payment. For integer months $n ≥ 1$,

$$L_0=P,\qquad L_n=L_{n-1}\left(1+\frac{R}{12}\right)-x.$$

Write $q=1+R/12$. The first two steps show the timing explicitly:

$$L_1=Pq-x,\qquad L_2=(Pq-x)q-x=Pq^2-xq-x.$$

The first payment has reduced the balance for one extra month, while the second payment has just been made. Repeated substitution gives

$$L_n=Pq^n-x(q^{n-1}+q^{n-2}+\cdots+q+1).$$

For $R\gt 0$, we have $q\gt 1$, so the geometric quotient is defined and gives

$$L_n=Pq^n-x\frac{q^n-1}{q-1}.$$

To finish the loan after $N$ months, set $L_N=0$, so

$$x=P\frac{(R/12)(1+R/12)^N}{(1+R/12)^N-1}.$$

The weighted payments form a finite geometric sum: payment $j$ contributes $xq^{n-j}$ to the reduction of the balance after payment $n$. This explains why the newest payment has weight one and the earliest has weight $q^{n-1}$. The resulting formula belongs to this fixed-rate, end-of-month payment model.

When $R=0$, use the recurrence directly instead of the quotient: $q=1$, $L_n=P-nx$, and $L_N=0$ gives $x=P/N$. No interest is charged in this case; the principal is divided equally among the payments.

Exercises

1. Let $a_n$ be the sequence $1,0,1,0,\ldots$ and let $b_n=a_{n+1}$. Find formulas for both sequences and verify $a_n+b_n=1$. Explain which formula changes when the first index is shifted.
2. Prove by induction that $1\cdot3\cdot5\cdots(2n-1)=(2n)!/(2^n n!)$. Compare the ratio of consecutive proposed values with the factor appended to the product.
3. Let $a_1=3$ and $a_{n+1}=a_n+4$. Find $a_n$ and $s_n$.
4. Let $b_1=5$ and $b_{n+1}=3b_n$. Find $b_n$ and the sum of the first $n$ terms.
5. Let $B_n=(\phi^n-\psi^n)/(\phi-\psi)$, where $\phi=(1+\sqrt5)/2$ and $\psi=(1-\sqrt5)/2$. Verify that $B_1=B_2=1$ and $B_{n+2}=B_{n+1}+B_n$.
6. Let $L_0=2000$ and $L_n=1.02L_{n-1}-150$. Write $L_n$ using a finite geometric sum.
7. Let $x_k=(2+3k)5(1/2)^k$ and $S_n=\sum_{k=0}^{n-1}x_k$. Write $S_n$ using the arithmetic-geometric formula.

Guided solutions

Solution · Model solution 1

Odd indices give $1$, and even indices give $0$, so $a_n=(1+(-1)^{n-1})/2$. Shifting one index gives $b_n=(1+(-1)^n)/2=1-a_n$. The alternating sign changes; the two complementary sequences therefore sum to $1$ at every index.

Solution · Model solution 2

At $n=1$, both sides equal $1$. If the identity holds at $n=k$, append the factor $2k+1$. The proposed right-hand side changes by exactly the same factor:

$$\frac{(2k+2)!}{2^{k+1}(k+1)!}\bigg/\frac{(2k)!}{2^k k!}=\frac{(2k+2)(2k+1)}{2(k+1)}=2k+1.$$

Thus the induction step holds. This proves the formula by its recurrence rather than repeating the separation into even and odd factors.

Solution · Model solution 3

This is arithmetic with first term $3$ and common difference $4$, hence $a_n=3+4(n-1)=4n-1$ and $s_n=n[2\cdot3+(n-1)4]/2=n(2n+1)$.

Solution · Model solution 4

This is geometric with first term $5$ and ratio $3$, so $b_n=5\cdot3^{n-1}$ and $s_n=5(3^n-1)/(3-1)=5(3^n-1)/2$.

Solution · Model solution 5

Since $\phi^2=\phi+1$ and $\psi^2=\psi+1$, multiplying by $\phi^n$ or $\psi^n$ gives $\phi^{n+2}=\phi^{n+1}+\phi^n$ and $\psi^{n+2}=\psi^{n+1}+\psi^n$. Subtract the two identities and divide by $\phi-\psi$ to obtain $B_{n+2}=B_{n+1}+B_n$. Also $B_1=1$ and $B_2=(\phi^2-\psi^2)/(\phi-\psi)=\phi+\psi=1$. Therefore $\{B_n\}$ satisfies the same initial values and recurrence as Fibonacci.

Solution · Model solution 6

Repeated substitution gives $L_n=2000(1.02)^n-150[(1.02)^{n-1}+\cdots+1]$, so $L_n=2000(1.02)^n-150((1.02)^n-1)/0.02$.

Solution · Model solution 7

Here $a=2$, $d=3$, $b=5$, and $r=1/2$. Therefore

$$S_n= \frac{10-(2+3n)5(1/2)^n}{1-1/2} +\frac{15(1/2)(1-(1/2)^n)}{(1-1/2)^2}.$$

This can be simplified further, but the important point is the substitution into the general finite-sum formula.