References: Rosen 8e §2.4 (sequences & summations), §8.1–8.2 (recurrences); Rudin, Principles of Mathematical Analysis, ch. 3; Spivak, Calculus, ch. 21–23.
2 / 32
1.1 Sequence — formal definition
Let $X$ be a non-empty set. A sequence in $X$ is a function $a : \mathbb{N} \to X$ (or $a : \mathbb{N}^* \to X$ — both indexings are used). The value $a(n)$ is written $a_n$ and called the $n$-th term. We denote the whole sequence by $(a_n)_{n \in \mathbb{N}}$, $(a_n)_{n \geq 0}$, or simply $(a_n)$.
A finite sequence of length $k$ is a function $\{0, 1, \dots, k-1\} \to X$ (or equivalently a $k$-tuple in $X^k$). An infinite sequence has domain $\mathbb{N}$.
$a_n := n^2$ gives $0, 1, 4, 9, 16, 25, \dots$ — a sequence in $\mathbb{N}$.
Let $(a_n)$ be a sequence in $X$ and $\varphi : \mathbb{N} \to \mathbb{N}$ a strictly increasing function. The composition $b_k := a_{\varphi(k)}$ defines a sequence $(b_k)$, called a subsequence of $(a_n)$. We often write $(a_{n_k})$ with $n_0 < n_1 < n_2 < \cdots$
From $a_n = (-1)^n$ extract the even-indexed subsequence $a_{2k} = 1, 1, 1, \dots$ and the odd-indexed subsequence $a_{2k+1} = -1, -1, -1, \dots$ Both are constant.
Every subsequence of a convergent sequence converges to the same limit.
Suppose $a_n \to L$. Given $\varepsilon > 0$, choose $N$ such that $|a_n - L| < \varepsilon$ for all $n \geq N$. Since $\varphi$ is strictly increasing, $\varphi(k) \to \infty$, so there exists $K$ with $\varphi(k) \geq N$ for all $k \geq K$. Then $|a_{\varphi(k)} - L| < \varepsilon$ for all $k \geq K$, i.e. $b_k \to L$. $\square$
bounded iff bounded both above and below, equivalently $\exists M \geq 0,\;\forall n,\; |a_n| \leq M$.
$(\sin n)$ is bounded by $1$. $(n)$ is bounded below by $0$ but not above. $((-1)^n n)$ is unbounded in both directions.
Every convergent real sequence is bounded.
Suppose $a_n \to L$. Take $\varepsilon = 1$: there is $N$ with $|a_n - L| < 1$ for all $n \geq N$, hence $|a_n| \leq |L| + 1$ for $n \geq N$. The finitely many terms $a_0, \dots, a_{N-1}$ are also bounded by $\max(|a_0|, \dots, |a_{N-1}|)$. Hence
$$\forall n,\;\; |a_n| \leq \max\bigl(|L| + 1,\, |a_0|,\, \dots,\, |a_{N-1}|\bigr). \;\square$$
Rudin, §3.2.
5 / 32
1.4 Monotone sequences
A real sequence $(a_n)$ is
increasing iff $a_n \leq a_{n+1}$ for all $n$; strictly increasing iff $a_n < a_{n+1}$;
decreasing iff $a_n \geq a_{n+1}$; strictly if $a_n > a_{n+1}$;
monotone iff increasing or decreasing.
$a_n = n^2$ is strictly increasing; $a_n = 1/(n+1)$ is strictly decreasing; $a_n = (-1)^n$ is not monotone.
Rudin, §3.13; Spivak, ch. 22.
6 / 32
2.1 Limit of a sequence — $\varepsilon$-$N$ definition
A real sequence $(a_n)$ converges to $L \in \mathbb{R}$, written $\lim_{n\to\infty} a_n = L$ or $a_n \to L$, iff
$$\forall \varepsilon > 0,\;\;\exists N \in \mathbb{N},\;\;\forall n \geq N,\;\;|a_n - L| < \varepsilon.$$
If no such $L$ exists, $(a_n)$ diverges. It diverges to $+\infty$ iff $\forall M,\;\exists N,\;\forall n \geq N,\; a_n > M$.
$a_n = (-1)^n$ diverges. If $a_n \to L$, take $\varepsilon = 1$: there is $N$ with $|(-1)^n - L| < 1$ for all $n \geq N$. But $a_N$ and $a_{N+1}$ differ by $2$, so by triangle inequality $2 = |a_N - a_{N+1}| \leq |a_N - L| + |L - a_{N+1}| < 2$ — contradiction.
Rudin, §3.1; Spivak, ch. 21.
7 / 32
2.2 Uniqueness of the limit
If $(a_n)$ converges, its limit is unique.
Suppose $a_n \to L_1$ and $a_n \to L_2$ with $L_1 \neq L_2$. Let $\varepsilon := |L_1 - L_2|/2 > 0$. There exist $N_1, N_2$ with $|a_n - L_1| < \varepsilon$ for $n \geq N_1$ and $|a_n - L_2| < \varepsilon$ for $n \geq N_2$. For $n \geq \max(N_1, N_2)$,
$$|L_1 - L_2| \leq |L_1 - a_n| + |a_n - L_2| < \varepsilon + \varepsilon = |L_1 - L_2|,$$
a strict inequality $|L_1 - L_2| < |L_1 - L_2|$ — contradiction. Hence $L_1 = L_2$. $\square$
Rudin, §3.2.
8 / 32
2.3 Algebra of limits
Let $a_n \to L$ and $b_n \to M$. Then
$a_n + b_n \to L + M$;
$\lambda \cdot a_n \to \lambda L$ for any $\lambda \in \mathbb{R}$;
$a_n \cdot b_n \to L \cdot M$;
if $M \neq 0$ and $b_n \neq 0$ for large $n$, then $a_n / b_n \to L / M$.
(1) Given $\varepsilon > 0$, choose $N_1$ with $|a_n - L| < \varepsilon/2$ and $N_2$ with $|b_n - M| < \varepsilon/2$ for indices past $N_1, N_2$. For $n \geq \max(N_1, N_2)$,
$|(a_n + b_n) - (L + M)| \leq |a_n - L| + |b_n - M| < \varepsilon.$ (3) Convergent sequences are bounded (slide 5): say $|b_n| \leq B$. Then
$|a_n b_n - LM| \leq |a_n b_n - L b_n| + |L b_n - LM| = |b_n| |a_n - L| + |L| |b_n - M| \leq B|a_n - L| + |L||b_n - M|.$
Make each term less than $\varepsilon/2$ for $n$ large. Other parts are similar. $\square$
Rudin Theorem 3.3.
9 / 32
2.4 Monotone convergence theorem
Every bounded monotone real sequence converges. Specifically: a bounded increasing sequence converges to its supremum; a bounded decreasing sequence converges to its infimum.
Let $(a_n)$ be increasing and bounded above; set $L := \sup\{a_n : n \in \mathbb{N}\}$, which exists by the least-upper-bound property of $\mathbb{R}$.
Let $\varepsilon > 0$. Since $L - \varepsilon < L$, $L - \varepsilon$ is not an upper bound, so there exists $N$ with $a_N > L - \varepsilon$. By monotonicity, $a_n \geq a_N$ for all $n \geq N$. Combined with $a_n \leq L$ (since $L$ is an upper bound), we get $L - \varepsilon < a_n \leq L < L + \varepsilon$, i.e. $|a_n - L| < \varepsilon$. Hence $a_n \to L$.
The decreasing case is symmetric (use infimum). $\square$
Define $a_n := \bigl(1 + \tfrac1n\bigr)^n$ on $n \geq 1$. One can show $(a_n)$ is increasing and bounded above by $3$, hence converges. The limit is the famous constant $e \approx 2.71828\ldots$
Rudin Theorem 3.14; Spivak, ch. 22.
10 / 32
2.5 Squeeze theorem
Let $(a_n), (b_n), (c_n)$ be real sequences with $a_n \leq b_n \leq c_n$ eventually (i.e. for all $n \geq N_0$). If $a_n \to L$ and $c_n \to L$, then $b_n \to L$.
Let $\varepsilon > 0$. Pick $N_1$ with $|a_n - L| < \varepsilon$ and $N_2$ with $|c_n - L| < \varepsilon$ for indices past them. For $n \geq \max(N_0, N_1, N_2)$,
$$L - \varepsilon < a_n \leq b_n \leq c_n < L + \varepsilon,$$
so $|b_n - L| < \varepsilon$. $\square$
Show $\dfrac{\sin n}{n} \to 0$. Since $-1 \leq \sin n \leq 1$, dividing by $n > 0$ gives $-\tfrac{1}{n} \leq \tfrac{\sin n}{n} \leq \tfrac{1}{n}$. Both bounds tend to $0$, so by the squeeze theorem $\tfrac{\sin n}{n} \to 0$.
Rudin Theorem 3.19; Spivak, ch. 21.
11 / 32
2.6 Cauchy sequences & Bolzano–Weierstrass
A real sequence $(a_n)$ is a Cauchy sequence iff
$$\forall \varepsilon > 0,\;\exists N,\;\forall m, n \geq N,\;|a_m - a_n| < \varepsilon.$$
Informally: the terms get arbitrarily close to each other, without referring to a limit.
In $\mathbb{R}$, a sequence is convergent iff it is Cauchy. ($\mathbb{R}$ is complete.)
(Convergent ⇒ Cauchy.) If $a_n \to L$, given $\varepsilon > 0$ pick $N$ with $|a_n - L| < \varepsilon/2$ for $n \geq N$. Then for $m, n \geq N$, $|a_m - a_n| \leq |a_m - L| + |L - a_n| < \varepsilon$. (Cauchy ⇒ Convergent in $\mathbb{R}$.) A Cauchy sequence is bounded (apply the definition with $\varepsilon = 1$). By Bolzano–Weierstrass it has a convergent subsequence $a_{n_k} \to L$. Using the Cauchy property, $a_n \to L$ as well. $\square$
Bolzano–Weierstrass. Every bounded real sequence has a convergent subsequence.
Rudin Theorems 3.6 (b), 3.11.
12 / 32
3.1 Arithmetic progression (AP)
A sequence $(a_n)_{n \geq 0}$ is an arithmetic progression with first term $a$ and common difference $d$ iff
$$a_n = a + n\,d \qquad\text{or equivalently}\qquad a_{n+1} - a_n = d \text{ for all } n.$$
The sum of the first $n$ terms ($n \geq 1$) of an AP is
$$S_n \;=\; \sum_{k=0}^{n-1} (a + kd) \;=\; \frac{n(2a + (n-1)d)}{2} \;=\; \frac{n(a_0 + a_{n-1})}{2}.$$
Gauss's pairing trick. Write $S$ forwards and backwards:
$$\begin{aligned} S &= a + (a+d) + (a+2d) + \cdots + (a + (n-1)d), \\ S &= (a + (n-1)d) + (a + (n-2)d) + \cdots + a. \end{aligned}$$
Adding column by column, each of the $n$ columns equals $2a + (n-1)d$ (a constant). Hence $2S = n \cdot (2a + (n-1)d)$, and $S = n(2a + (n-1)d)/2$. $\square$
$\displaystyle 1 + 2 + 3 + \cdots + n \;=\; \frac{n(n+1)}{2}$ (take $a = 1$, $d = 1$, sum from $a_0$ to $a_{n-1}$, with $n$ replaced by $n+1$ indices).
Rosen 8e §2.4 Table 2; Spivak, ch. 2 Prob. 1.
13 / 32
3.2 Geometric progression (GP)
A sequence $(a_n)_{n \geq 0}$ is a geometric progression with first term $a$ (assumed non-zero) and common ratio $r$ iff
$$a_n = a \cdot r^n \qquad\text{or equivalently}\qquad \frac{a_{n+1}}{a_n} = r \text{ for all } n.$$
The sum of the first $n$ terms ($n \geq 1$) of a GP is
$$S_n \;=\; \sum_{k=0}^{n-1} a r^k \;=\; \begin{cases} a \cdot \dfrac{1 - r^n}{1 - r} & \text{if } r \neq 1, \\ n \cdot a & \text{if } r = 1. \end{cases}$$
For $r = 1$ the sum is trivially $n \cdot a$. For $r \neq 1$, write
$$S_n = a + ar + ar^2 + \cdots + ar^{n-1},$$
$$r S_n = \phantom{a +\;} ar + ar^2 + \cdots + ar^{n-1} + ar^n.$$
Subtract: $S_n - r S_n = a - ar^n$, so $(1 - r) S_n = a(1 - r^n)$, giving $S_n = a(1 - r^n)/(1 - r)$. $\square$
The infinite geometric series $\sum_{k=0}^{\infty} a r^k$ converges iff $|r| < 1$, in which case its sum is $\dfrac{a}{1 - r}$.
If $|r| < 1$, $r^n \to 0$ (proved on slide 16), so $S_n \to a/(1-r)$. If $|r| \geq 1$ and $a \neq 0$, $|a r^n| \geq |a| \not\to 0$, so the necessary condition $a_n \to 0$ fails (slide 18) and the series diverges. $\square$
Rosen 8e §2.4; Rudin §3.26.
14 / 32
3.3 Standard closed-form sums
Sum
Closed form
$\displaystyle \sum_{k=1}^{n} k$
$\dfrac{n(n+1)}{2}$
$\displaystyle \sum_{k=1}^{n} k^2$
$\dfrac{n(n+1)(2n+1)}{6}$
$\displaystyle \sum_{k=1}^{n} k^3$
$\left(\dfrac{n(n+1)}{2}\right)^{\!2}$
$\displaystyle \sum_{k=0}^{n-1} r^k$, $r \neq 1$
$\dfrac{1 - r^n}{1 - r}$
$\displaystyle \sum_{k=0}^{n} \binom{n}{k}$
$2^n$ (binomial theorem at $x = y = 1$)
Proof of $\sum k^2 = n(n+1)(2n+1)/6$ by induction
Base ($n = 1$). LHS $= 1$, RHS $= 1 \cdot 2 \cdot 3 / 6 = 1$. ✓ Inductive step. Assume true at $n$. Then $\sum_{k=1}^{n+1} k^2 = \tfrac{n(n+1)(2n+1)}{6} + (n+1)^2 = \tfrac{(n+1)\bigl[n(2n+1) + 6(n+1)\bigr]}{6} = \tfrac{(n+1)(2n^2 + 7n + 6)}{6} = \tfrac{(n+1)(n+2)(2n+3)}{6}$, which is the formula at $n+1$. $\square$
Rosen 8e §2.4 Table 2.
15 / 32
3.4 Standard limits
If $|r| < 1$, then $r^n \to 0$.
If $|r| > 1$, then $|r^n| \to +\infty$.
$\dfrac{n^k}{r^n} \to 0$ for any fixed $k \geq 0$ and $|r| > 1$ — exponentials beat polynomials.
$n^{1/n} \to 1$.
(1) Write $|r| = 1/(1 + h)$ with $h > 0$. By Bernoulli's inequality, $(1 + h)^n \geq 1 + nh$, so $|r^n| = 1/(1+h)^n \leq 1/(1 + nh) \to 0$. Hence $r^n \to 0$ by the squeeze theorem. (2) Apply (1) to $1/r$. (3) Write $r = 1 + h$ with $h > 0$. By the binomial theorem, for $n > k$:
$r^n = (1+h)^n \geq \binom{n}{k+1} h^{k+1} \geq \frac{(n - k)^{k+1}}{(k+1)!} \, h^{k+1}.$
Hence $\dfrac{n^k}{r^n} \leq \dfrac{(k+1)! \cdot n^k}{(n-k)^{k+1} h^{k+1}} \to 0$ as $n \to \infty$. $\square$
Rudin §3.20.
16 / 32
4.1 Series — partial sums
Given a real sequence $(a_n)_{n \geq 0}$, the series $\sum_{n=0}^{\infty} a_n$ is the formal object whose $n$-th partial sum is
$$S_n \;:=\; \sum_{k=0}^{n} a_k \;=\; a_0 + a_1 + \cdots + a_n.$$
The series converges iff the sequence $(S_n)$ converges; in that case its sum is $\sum_{n=0}^{\infty} a_n := \lim_{n \to \infty} S_n$. Otherwise the series diverges.
Crucially, a series is just a special sequence — the sequence of its partial sums — so every result about sequence convergence applies.
The geometric series $\sum_{n=0}^{\infty} r^n$ has partial sums $S_n = (1 - r^{n+1})/(1-r)$; converges to $1/(1-r)$ iff $|r| < 1$ (slide 14).
Rudin §3.21; Spivak ch. 23.
17 / 32
4.2 Necessary condition $a_n \to 0$ — and the harmonic series
If $\sum a_n$ converges, then $a_n \to 0$.
Let $S := \lim S_n$. Then $a_n = S_n - S_{n-1} \to S - S = 0$. $\square$
The converse is false: $a_n \to 0$ does not imply $\sum a_n$ converges. The counter-example is the harmonic series.
Oresme (c. 1350). The harmonic series $\;\sum_{n=1}^{\infty} \dfrac{1}{n}\;$ diverges, even though $\tfrac{1}{n} \to 0$.
Group the terms in blocks of doubling length:
$$\underbrace{\tfrac{1}{1}}_{\geq \tfrac12} + \underbrace{\tfrac{1}{2}}_{\geq \tfrac12} + \underbrace{\tfrac{1}{3} + \tfrac{1}{4}}_{\geq \tfrac12} + \underbrace{\tfrac{1}{5} + \tfrac{1}{6} + \tfrac{1}{7} + \tfrac{1}{8}}_{\geq \tfrac12} + \cdots$$
The $k$-th block has $2^{k-1}$ terms, each at least $1/2^k$, summing to at least $1/2$. Hence $S_{2^n} \geq 1 + n/2 \to \infty$. So $(S_n)$ is unbounded and the series diverges. $\square$
Rudin §3.28; Spivak ch. 23.
18 / 32
4.3 Telescoping series
Let $(b_n)$ be a sequence with $b_n \to L$. Define $a_n := b_n - b_{n+1}$. Then $\sum_{n=0}^{\infty} a_n = b_0 - L$.
The $n$-th partial sum telescopes:
$$S_n = \sum_{k=0}^{n} (b_k - b_{k+1}) = b_0 - b_{n+1}.$$
As $n \to \infty$, $b_{n+1} \to L$, so $S_n \to b_0 - L$. $\square$
$\displaystyle \sum_{n=1}^{\infty} \frac{1}{n(n+1)}$. Write $\tfrac{1}{n(n+1)} = \tfrac{1}{n} - \tfrac{1}{n+1}$. With $b_n = 1/n$ (and $L = 0$), the sum telescopes to $b_1 - 0 = 1$.
The series $\;\sum_{n=1}^{\infty} \dfrac{1}{n^p}\;$ converges iff $p > 1$.
If $p \leq 1$: for $n \geq 1$, $1/n^p \geq 1/n$, so by comparison with the harmonic series (which diverges, slide 18), the series diverges. If $p > 1$: the function $f(x) = 1/x^p$ is positive and decreasing for $x \geq 1$, so by the integral test (slide 22) the series converges iff $\int_1^{\infty} x^{-p}\,dx$ converges. Compute:
$$\int_1^{\infty} x^{-p}\,dx = \lim_{R\to\infty}\frac{R^{1-p} - 1}{1 - p} = \frac{1}{p - 1} < \infty.$$
Hence the series converges. $\square$
$\sum 1/n^2$ converges (Euler: $= \pi^2/6$). $\sum 1/n^{1/2}$ diverges. $\sum 1/(n \ln n)$ diverges (a borderline case, treated by the integral test with $f(x) = 1/(x \ln x)$).
The partial sums of $\sum a_n$ are bounded above by those of $\sum b_n$. Since $(a_n)$ are non-negative, the partial sums of $\sum a_n$ are increasing; bounded + increasing ⇒ convergent (slide 10). The contrapositive gives the second statement. $\square$
Ratio test (d'Alembert). Let $a_n > 0$ and suppose $L := \lim_{n\to\infty} a_{n+1}/a_n$ exists.
If $L < 1$, $\sum a_n$ converges.
If $L > 1$, $\sum a_n$ diverges.
If $L = 1$, the test is inconclusive.
Suppose $L < 1$ and pick $r$ with $L < r < 1$. For $n \geq N$ large, $a_{n+1}/a_n < r$, so $a_{N+k} < a_N \cdot r^k$. Hence $\sum_{k \geq 0} a_{N+k} < a_N \sum r^k < \infty$ (geometric). By comparison, $\sum a_n$ converges. If $L > 1$, the same argument shows $a_n$ grows exponentially, so $a_n \not\to 0$ and the series diverges. $\square$
Rudin §3.34, §3.41.
21 / 32
4.6 Root and integral tests
Root test (Cauchy). Let $a_n \geq 0$ and $L := \limsup_{n \to \infty} \sqrt[n]{a_n}$.
If $L < 1$, $\sum a_n$ converges.
If $L > 1$, $\sum a_n$ diverges.
If $L = 1$, the test is inconclusive.
If $L < 1$, pick $r$ with $L < r < 1$. For $n$ large, $\sqrt[n]{a_n} < r$, so $a_n < r^n$ and comparison with the geometric series gives convergence. If $L > 1$, $a_n \geq 1$ for infinitely many $n$, so $a_n \not\to 0$. $\square$
Integral test. Let $f : [1, \infty) \to [0, \infty)$ be positive, decreasing and continuous. Then $\sum_{n=1}^{\infty} f(n)$ converges iff $\int_1^{\infty} f(x)\,dx$ converges. Moreover
$$\int_1^{N+1} f(x)\,dx \;\leq\; \sum_{n=1}^{N} f(n) \;\leq\; f(1) + \int_1^{N} f(x)\,dx.$$
Compare $f$ with the step function constant on $[n, n+1)$ equal to $f(n)$: since $f$ is decreasing, $f(n+1) \leq f(x) \leq f(n)$ on $[n, n+1]$, giving $f(n+1) \leq \int_n^{n+1} f \leq f(n)$. Sum from $n = 1$ to $N$. $\square$
Rudin §3.33; Spivak ch. 23.
22 / 32
4.7 Alternating series — Leibniz test
Let $(b_n)$ be a real sequence with $b_n \geq 0$, $(b_n)$ decreasing, and $b_n \to 0$. Then the alternating series $\sum_{n=0}^{\infty} (-1)^n b_n$ converges. Moreover, the truncation error is bounded: $\bigl|S - S_N\bigr| \leq b_{N+1}$.
Let $S_n = \sum_{k=0}^{n} (-1)^k b_k$. The even partial sums $(S_{2m})$ are decreasing:
$S_{2m+2} - S_{2m} = -b_{2m+1} + b_{2m+2} \leq 0$ (since $(b_n)$ is decreasing).
The odd partial sums $(S_{2m+1})$ are increasing:
$S_{2m+3} - S_{2m+1} = b_{2m+2} - b_{2m+3} \geq 0$.
Also $S_{2m+1} = S_{2m} - b_{2m+1} \leq S_{2m}$. So $(S_{2m})$ is decreasing and bounded below (by $S_1$), and $(S_{2m+1})$ is increasing and bounded above (by $S_0$); both converge by monotone convergence (slide 10). Their difference $S_{2m} - S_{2m+1} = b_{2m+1} \to 0$, so both limits coincide. Hence $S_n \to S$.
The error bound follows because $S$ lies between consecutive partial sums. $\square$
$\displaystyle \sum_{n=1}^{\infty} \frac{(-1)^{n+1}}{n} = 1 - \tfrac12 + \tfrac13 - \tfrac14 + \cdots = \ln 2$. Converges by Leibniz; does not converge absolutely (the harmonic series diverges). This is a conditionally convergent series — see next slide.
Rudin §3.43; Spivak ch. 23.
23 / 32
4.8 Absolute vs conditional convergence
$\sum a_n$ converges absolutely iff $\sum |a_n|$ converges. It converges conditionally iff $\sum a_n$ converges but $\sum |a_n|$ diverges.
Absolute convergence implies convergence: if $\sum |a_n|$ converges, so does $\sum a_n$.
Write $a_n = a_n^+ - a_n^-$ where $a_n^+ := \max(a_n, 0)$, $a_n^- := \max(-a_n, 0)$. Both are non-negative and bounded by $|a_n|$, so by comparison both $\sum a_n^+$ and $\sum a_n^-$ converge, hence so does their difference $\sum a_n$. $\square$
Riemann's rearrangement theorem. A conditionally convergent real series can be rearranged so as to converge to any prescribed real number — or to diverge.
This shocking result shows that for conditional series the value of the sum depends on the order of summation; only absolutely convergent series behave "like finite sums" under rearrangement (Dirichlet's theorem).
Rudin §3.45–3.55.
24 / 32
5.1 Recurrence relations
A recurrence relation for a sequence $(a_n)$ is an equation expressing $a_n$ in terms of finitely many previous terms $a_{n-1}, a_{n-2}, \dots, a_{n-k}$, together with $k$ initial values $a_0, \dots, a_{k-1}$. The integer $k$ is the order of the recurrence.
Fibonacci: $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. First terms: $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \dots$
Factorial: $0! = 1$ and $n! = n \cdot (n-1)!$ for $n \geq 1$ — first-order, non-linear.
A recurrence is linear homogeneous with constant coefficients of order $k$ iff it has the form
$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} \qquad (c_k \neq 0, \; c_i \in \mathbb{R}).$$
Rosen 8e §8.2.
25 / 32
5.2 Solving linear homogeneous recurrences
Consider the order-$k$ linear homogeneous recurrence $a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}$. Its characteristic equation is
$$x^k = c_1 x^{k-1} + c_2 x^{k-2} + \cdots + c_k.$$
If the equation has $k$ distinct real roots $r_1, \dots, r_k$, then every solution of the recurrence is of the form
$$a_n = \alpha_1 r_1^n + \alpha_2 r_2^n + \cdots + \alpha_k r_k^n,$$
where the constants $\alpha_i$ are determined by the $k$ initial values.
First, each $a_n = r^n$ with $r$ a root of the characteristic equation satisfies the recurrence: substituting gives $r^n = c_1 r^{n-1} + \cdots + c_k r^{n-k}$, dividing by $r^{n-k}$ recovers the characteristic equation.
Linearity of the recurrence means any linear combination of solutions is again a solution. The Vandermonde matrix on the first $k$ values is invertible (since the $r_i$ are distinct), so the $k$ initial values determine the $k$ coefficients $\alpha_i$ uniquely. By induction the whole sequence is then determined, matching the linear combination. $\square$
Rosen 8e §8.2 Theorem 1.
26 / 32
5.3 Binet's formula for Fibonacci — proved
Let $\varphi = \dfrac{1 + \sqrt 5}{2}$ (golden ratio) and $\psi = \dfrac{1 - \sqrt 5}{2}$. Then for every $n \geq 0$:
$$F_n \;=\; \frac{\varphi^n - \psi^n}{\sqrt 5}.$$
The recurrence $F_n = F_{n-1} + F_{n-2}$ has characteristic equation $x^2 = x + 1$, i.e. $x^2 - x - 1 = 0$, with roots
$$r_{1,2} = \frac{1 \pm \sqrt 5}{2} \;=\; \varphi,\;\psi.$$
By the theorem of slide 26, $F_n = \alpha \varphi^n + \beta \psi^n$ for some constants $\alpha, \beta$. Use the initial conditions:
$$F_0 = 0 \;\Rightarrow\; \alpha + \beta = 0, \qquad F_1 = 1 \;\Rightarrow\; \alpha \varphi + \beta \psi = 1.$$
From the first, $\beta = -\alpha$. Substituting: $\alpha(\varphi - \psi) = 1$, i.e. $\alpha \sqrt 5 = 1$, hence $\alpha = 1/\sqrt 5$, $\beta = -1/\sqrt 5$. Therefore
$$F_n = \frac{\varphi^n - \psi^n}{\sqrt 5}. \;\square$$
Since $|\psi| < 1$, $\psi^n \to 0$, so $F_n \sim \varphi^n / \sqrt 5$ — Fibonacci grows like a geometric progression with ratio $\varphi \approx 1.618$. Concretely, $F_n$ is the nearest integer to $\varphi^n / \sqrt 5$ for every $n \geq 0$.
Rosen 8e §8.2 Example 6.
27 / 32
6. Products $\prod$
For a sequence $(a_n)$ and integers $m \leq n$:
$$\prod_{k=m}^{n} a_k \;:=\; a_m \cdot a_{m+1} \cdots a_n.$$
Empty-product convention. If $m > n$, the product is defined to be $1$ (the multiplicative identity). Similarly, the empty sum is $0$.
The factorial is $n! = \prod_{k=1}^{n} k$. With the empty-product convention, $0! = 1$.
Many of these are catalogued in the On-Line Encyclopedia of Integer Sequences (OEIS). Catalan numbers count an astonishing number of combinatorial objects — triangulations of polygons, well-balanced parentheses, lattice paths, binary trees, etc.