Section 33.2

Sequences, Series and Estimation

Limits, Fibonacci identities, infinite sums and generating functions, estimating sizes such as the digits of 100!.

Toolkit

These problems combine linear recurrences, generating functions, and logarithmic estimation. For sequences satisfying $a_n = a_{n-1}+a_{n-2}$ (or similar linear recurrences), fixed points and ratios solve $L=1+1/L$ type equations, and errors/perturbations propagate obeying the same recurrence. Key tools:

Fibonacci generating function: $\sum_{n\ge0} F_n x^n = \dfrac{x}{1-x-x^2}$ .
Taylor/power series extraction: $f^{(n)}(0) = n!\,[x^n]f(x)$ ; use Cauchy products, keeping only contributing term combinations.
For power sums, $\sum_{k=1}^n k^m \sim \dfrac{n^{m+1}}{m+1}$ via the Riemann sum $\int_0^1 x^m\,dx$ .
For $U\sim\mathrm{Unif}(0,1)$ , $\mathbb{E}\left[\dfrac{1}{1-U}\right]$ -type sums: expand geometrically and use $\mathbb{E}[U^n]=\frac{1}{n+1}$ .
A fraction $1/k$ terminates in base 10 iff $k=2^a5^b$ ; such sums factor as products of geometric series $\sum 2^{-a}\sum 5^{-b}$ .
Digit count of $N$ : $\lfloor \log_{10}N\rfloor+1$ ; use Stirling’s approximation $\ln n! \approx n\ln n - n + \tfrac12\ln(2\pi n)$ for factorials.
$\log_{10}2+\log_{10}5=1$ exactly, useful for floor-sum identities on concatenated numbers.

Problems