08 Sequences and Recurrences

A structured guide to describing sequences, simplifying sums, modeling and solving recurrence relations, using generating functions, and analyzing recursive algorithms.

Describing Sequences

A is an ordered list whose terms are indexed. It may be written as $a_0,a_1,a_2,\ldots$ , or as a function $a:\mathbb{N}\to\mathbb{R}$ . Always identify the starting index, because a formula based at $0$ differs from one based at $1$ .

There are two common ways to describe a :

A gives a term directly. For example, $a_n=3n+2$ gives $a_0=2$ , $a_1=5$ , and $a_2=8$ .
A gives initial value or values and a rule for obtaining later terms. For example,

a_0=2,\qquad a_n=a_{n-1}+3\quad(n\ge 1).

This produces $2,5,8,11,\ldots$ . A recurrence rule alone is generally insufficient; the initial conditions identify which satisfies the rule.

Takeaway: Before manipulating a , determine its indexing convention and whether it is described directly or recursively.

Arithmetic and Geometric Patterns

Two important families are recognized by how neighboring terms are related.

An has constant difference $d$ :

a_n=a_0+nd.

The sum of its first $n+1$ terms is

\sum_{k=0}^{n}a_k=\frac{n+1}{2}(a_0+a_n).

A has constant ratio $r$ :

a_n=a_0r^n.

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

\sum_{k=0}^{n}a_0r^k=a_0\frac{1-r^{n+1}}{1-r}.

If $|r|<1$ , the infinite geometric series converges and

\sum_{k=0}^{\infty}a_0r^k=\frac{a_0}{1-r}.

To classify a , subtract consecutive terms to test for an arithmetic pattern and divide consecutive terms, where defined, to test for a geometric pattern.

Takeaway: Constant differences lead to arithmetic formulas; constant ratios lead to geometric formulas and, under $|r|<1$ , a useful infinite sum.

Summation Techniques

Summation notation compresses a list of additions:

\sum_{k=m}^{n}f(k)=f(m)+f(m+1)+\cdots+f(n).

Linearity allows sums to be separated:

\sum_{k=m}^{n}\bigl(cf(k)+dg(k)\bigr)=c\sum_{k=m}^{n}f(k)+d\sum_{k=m}^{n}g(k).

Important standard sums are

\sum_{k=1}^{n}k=\frac{n(n+1)}{2},

\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6},

and

\sum_{k=1}^{n}k^3=\left(\frac{n(n+1)}{2}\right)^2.

A sum telescopes when adjacent terms cancel. If $f(k)=g(k+1)-g(k)$ , then

\sum_{k=m}^{n}f(k)=g(n+1)-g(m).

For example,

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

Reindexing changes the index and its bounds together. Setting $j=k-1$ gives

\sum_{k=1}^{n}a_{k-1}=\sum_{j=0}^{n-1}a_j.

Takeaway: When simplifying a sum, use linearity, look for cancellation, and change bounds whenever the index changes.

Building Recurrence Models

A defines a term from earlier terms. Its order is the number of previous terms required. For example, $a_n=4a_{n-1}-a_{n-2}$ has order $2$ . A recurrence becomes a complete only after enough initial conditions are supplied.

The Fibonacci illustrates this structure:

F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}\quad(n\ge 2).

To model a counting problem with a recurrence:

Define exactly what $a_n$ counts or measures.
Partition the objects into disjoint cases.
Relate each case to a smaller instance.
State the initial conditions.
Check the first few values.

For tilings of a $1\times n$ board by squares of length $1$ and dominoes of length $2$ , the final tile is either a square or a domino. Therefore,

a_n=a_{n-1}+a_{n-2},\qquad a_0=1,\quad a_1=1.

The value $a_0=1$ counts the one empty tiling.

Takeaway: A well-constructed recurrence comes from disjoint cases, smaller instances, and explicit initial conditions.

Solving Linear Recurrences

For a homogeneous linear recurrence with constant coefficients,

a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k},

try a solution of the form $a_n=r^n$ . This produces the

r^k-c_1r^{k-1}-c_2r^{k-2}-\cdots-c_k=0.

If the roots $r_1,\ldots,r_k$ are distinct, the general solution is

a_n=C_1r_1^n+C_2r_2^n+\cdots+C_kr_k^n.

The constants are found from the initial conditions. For example,

a_n=5a_{n-1}-6a_{n-2},\qquad a_0=1,\quad a_1=2

has

r^2-5r+6=(r-2)(r-3)=0.

Thus $a_n=A2^n+B3^n$ . The initial conditions give $A+B=1$ and $2A+3B=2$ , so $A=1$ , $B=0$ , and

a_n=2^n.

If a root $r$ has multiplicity $m$ , its contribution is

(C_0+C_1n+\cdots+C_{m-1}n^{m-1})r^n.

For a nonhomogeneous recurrence, write the solution as

a_n=a_n^{(h)}+a_n^{(p)},

where the first term solves the associated homogeneous recurrence and the second is one particular solution. Choose the trial form for the particular solution from the shape of the forcing term; if it duplicates a homogeneous solution, multiply the trial by a sufficient power of $n$ .

Takeaway: Find the characteristic roots, construct the correct general form, and use initial conditions to determine its constants.

Generating Functions

An ordinary packages the terms of a into a formal power series:

A(x)=\sum_{n=0}^{\infty}a_nx^n.

To use this method, multiply the recurrence by $x^n$ , sum over the valid indices, and express the resulting shifted sums in terms of $A(x)$ .

Consider

a_n=3a_{n-1}-2a_{n-2},\qquad a_0=1,\quad a_1=3.

Summing after multiplication by $x^n$ gives

A(x)-1-3x=3x(A(x)-1)-2x^2A(x).

Solving for the yields

A(x)=\frac{1}{1-3x+2x^2}=\frac{1}{(1-x)(1-2x)}.

Partial fractions give

A(x)=-\frac{1}{1-x}+\frac{2}{1-2x},

so the is

a_n=2^{n+1}-1.

Generating functions are especially useful for counting problems and for recurrences whose algebra is difficult to handle directly.

Takeaway: Generating functions turn shifts in a recurrence into algebraic factors, allowing the to be recovered from a power-series identity.

Recursion in Algorithms and Counting

Recursion also describes algorithms. A recursive algorithm needs a , which is solved directly, and a recursive case, which reduces the input toward that .

For factorial,

0!=1,\qquad n!=n(n-1)!\quad(n\ge 1).

If $T(n)$ counts multiplication operations, then

T(n)=T(n-1)+1,\qquad T(0)=0,

so $T(n)=n$ . The running time is therefore linear in $n$ .

split a problem into smaller subproblems and combine their solutions. If a problem of size $n$ is divided into two subproblems of size approximately $n/2$ , a typical recurrence is

T(n)=2T(n/2)+cn.

This describes the pattern of merge sort: two recursive sorting calls followed by linear-time merging. Its running time is $O(n\log n)$ .

Recurrences also arise in counting. If $s_n$ counts lists with entries from $\{1,2,3\}$ whose entries sum to $n$ , classifying by the first entry gives

s_n=s_{n-1}+s_{n-2}+s_{n-3},

with $s_0=1$ and $s_n=0$ for $n<0$ .

Takeaway: To analyze a recursive process, identify its stopping condition, describe how one step reduces the problem, and translate that structure into a recurrence.