Quiz 2
Registry Synced

Recurrence Relations

371 words
2 min read

Reading compass

Now · 3.1 Intuition: Defining Sequences Recursively

Recurrence Relations

3.1 Intuition: Defining Sequences Recursively

A recurrence defines each term of a sequence in terms of previous terms. The Fibonacci numbers Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2} are the most famous example.
🔑 Key Insight: Many counting problems naturally yield recurrence relations.

3.2 Linear Homogeneous Recurrences

Form: an=c1an−1+c2an−2+⋯+ckan−ka_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} Characteristic equation: rk−c1rk−1−c2rk−2−⋯−ck=0r^k - c_1 r^{k-1} - c_2 r^{k-2} - \cdots - c_k = 0 Solution:
  • Distinct roots r1,…,rkr_1, \dots, r_k: an=α1r1n+⋯+αkrkna_n = \alpha_1 r_1^n + \cdots + \alpha_k r_k^n
  • Repeated root rr with multiplicity mm: (α1+α2n+⋯+αmnm−1)rn(\alpha_1 + \alpha_2 n + \cdots + \alpha_m n^{m-1}) r^n

Example: Fibonacci

Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}, F0=0F_0 = 0, F1=1F_1 = 1 Characteristic: r2−r−1=0  ⟹  r=1±52r^2 - r - 1 = 0 \implies r = \frac{1 \pm \sqrt{5}}{2} Fn=15(ϕn−(−ϕ)−n)F_n = \frac{1}{\sqrt{5}}(\phi^n - (-\phi)^{-n}) where ϕ=1+52\phi = \frac{1+\sqrt{5}}{2}

3.3 Non-Homogeneous Recurrences

Form: an=c1an−1+⋯+ckan−k+f(n)a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k} + f(n) Solution = homogeneous solution + particular solution.

Example: an=2an−1+3a_n = 2a_{n-1} + 3, a0=1a_0 = 1

Homogeneous: an(h)=α⋅2na_n^{(h)} = \alpha \cdot 2^n Particular: Try constant cc: c=2c+3  ⟹  c=−3c = 2c + 3 \implies c = -3 General: an=α⋅2n−3a_n = \alpha \cdot 2^n - 3, a0=1  ⟹  α=4a_0 = 1 \implies \alpha = 4 Solution: an=4⋅2n−3=2n+2−3a_n = 4 \cdot 2^n - 3 = 2^{n+2} - 3

✅ Practice Questions

Q1: Solve an=3an−1−2an−2a_n = 3a_{n-1} - 2a_{n-2}, a0=1a_0 = 1, a1=2a_1 = 2.
Solution
r2−3r+2=0  ⟹  r=1,2r^2 - 3r + 2 = 0 \implies r = 1, 2 an=α⋅1n+β⋅2n=α+β⋅2na_n = \alpha \cdot 1^n + \beta \cdot 2^n = \alpha + \beta \cdot 2^n a0=α+β=1a_0 = \alpha + \beta = 1, a1=α+2β=2  ⟹  β=1,α=0a_1 = \alpha + 2\beta = 2 \implies \beta = 1, \alpha = 0 an=2na_n = 2^n Q2: Solve an=4an−1−4an−2a_n = 4a_{n-1} - 4a_{n-2}, a0=0a_0 = 0, a1=2a_1 = 2. Solution
r2−4r+4=0  ⟹  (r−2)2=0r^2 - 4r + 4 = 0 \implies (r-2)^2 = 0, repeated root r=2r=2. an=(α+βn)⋅2na_n = (\alpha + \beta n) \cdot 2^n a0=α=0a_0 = \alpha = 0, a1=(0+β)⋅2=2  ⟹  β=1a_1 = (0 + \beta) \cdot 2 = 2 \implies \beta = 1 an=n⋅2na_n = n \cdot 2^n Join Discord PreviousPigeonhole & Inclusion-ExclusionNextRecurrence Applications
Document outline

Keep your place and jump directly to a heading.

Table of Contents
System Normal // Awaiting Context

Intelligence Hub

Navigate the knowledge graph to generate context. The Hub adapts dynamically to surface backlinks, related notes, and metadata insights.

Open library →Launch Assessment Engine