uniolympiads Ελληνικά

Recursive sequences and series

xn+1=f(xn)x_{n+1} = f(x_n) depending on the monotonicity of ff, contractions, linear recurrences, and summation by parts (Abel) with the Dirichlet test.

xn+1=f(xn)x_{n+1} = f(x_n)

Let f ⁣:I→If\colon I \to I be continuous and x0∈Ix_0 \in I.

  • If ff is increasing, (xn)(x_n) is monotone: increasing if x1≥x0x_1 \ge x_0, decreasing if x1≤x0x_1 \le x_0. Induction: xn≤xn+1⇒f(xn)≤f(xn+1)x_{n} \le x_{n+1} \Rightarrow f(x_n) \le f(x_{n+1}).
  • If ff is decreasing, f∘ff \circ f is increasing. The subsequences (x2n)(x_{2n}) and (x2n+1)(x_{2n+1}) are monotone in opposite directions. Check separately whether they have the same limit.
  • Bounded and monotone ⇒ converges. The limit LL satisfies L=f(L)L = f(L), by continuity.
  • Contraction. If ∣f′(x)∣≤q<1|f'(x)| \le q < 1 on II, then ∣xn+1−L∣≤q ∣xn−L∣|x_{n+1} - L| \le q\,|x_n - L|, so ∣xn−L∣≤qn∣x0−L∣|x_n - L| \le q^n |x_0 - L| and the fixed point LL is unique.

Linear recurrences. For xn+2=p xn+1+q xnx_{n+2} = p\,x_{n+1} + q\,x_n solve r2=pr+qr^2 = p r + q. With roots r1≠r2r_1 \ne r_2, xn=Ar1n+Br2nx_n = A r_1^n + B r_2^n. With a double root rr, xn=(A+Bn)rnx_n = (A + Bn) r^n. A,BA, B come from the first two terms.

For the speed of convergence, see Stolz–Cesàro and Taylor.

Series

  • Necessary condition: if ∑an\sum a_n converges, then an→0a_n \to 0. The converse is false: ∑1n=∞\sum \frac1n = \infty.
  • Comparison and limit comparison with ∑1np\sum \frac{1}{n^p}, which converges if and only if p>1p > 1.
  • Cauchy condensation: for non-increasing an≥0a_n \ge 0, ∑an\sum a_n converges if and only if ∑2ka2k\sum 2^k a_{2^k} converges. This shows that ∑1nln⁡n\sum \frac{1}{n \ln n} diverges.

Summation by parts (Abel). With Ak=a1+⋯+akA_k = a_1 + \dots + a_k:

∑k=1nakbk=Anbn−∑k=1n−1Ak (bk+1−bk).\sum_{k=1}^{n} a_k b_k = A_n b_n - \sum_{k=1}^{n-1} A_k \,(b_{k+1} - b_k) .

It is the discrete analogue of integration by parts. It gives the Dirichlet test: if the AnA_n are bounded and (bn)(b_n) decreases monotonically to 00, then ∑anbn\sum a_n b_n converges. Example: ∑sin⁡kk\sum \frac{\sin k}{k} converges, because ∣∑k=1nsin⁡k∣≤1sin⁡(1/2)\big|\sum_{k=1}^{n} \sin k\big| \le \frac{1}{\sin(1/2)}.

Pitfalls

  • Don't solve L=f(L)L = f(L) before proving convergence. For xn+1=2xnx_{n+1} = 2x_n, x0=1x_0 = 1, the equation gives L=0L = 0, while xn=2n→∞x_n = 2^n \to \infty.
  • Several fixed points: when L=f(L)L = f(L) has several solutions, the limit depends on x0x_0. Show which interval the sequence stays in.
  • Rearrangement. A conditionally convergent series, such as ∑(−1)n+1n\sum \frac{(-1)^{n+1}}{n}, can be rearranged to converge to any number (Riemann). Rearrange freely only absolutely convergent series.

Further reading

  • Abbott, Understanding Analysis, 2nd ed., §2.4 (The Monotone Convergence Theorem)
  • Gelca & Andreescu, Putnam and Beyond, §3.1.2 (Linear Recursive Sequences)
  • Kaczor & Nowak, Problems in Mathematical Analysis I, §2.1 (Monotonic Sequences)
  • Gelca & Andreescu, Putnam and Beyond, §3.2.4 (Derivatives and Their Applications)
  • Gelca & Andreescu, Putnam and Beyond, §3.1.5 (Series (problem 361, solved with Abel summation))

Contest problems using these tools

No problems with these tools yet.