Please enable JavaScript.
Coggle requires JavaScript to display documents.
Topic 3: Recursion & Induction, 2, 3, General form, n-th term, Sum,…
Topic 3: Recursion & Induction
Arithmetic Sequence
a, a+d, a+2d, a+3d, ...
aₙ = a + (n - 1)d
aₙ = aₙ₋₁ + d, n ≥ 2
Sₙ = n/2 [2a + (n - 1)d]
Geometric Sequence
a, ar, ar², ar³, ar⁴, ...
aₙ = arⁿ⁻¹
Sₙ = a(1 - rⁿ) / (1 - r), r ≠ 1
Mathematical induction
n²
n(n+1)/2
[P(1) ∧ ∀k (P(k) → P(k+1))] ⇒ ∀n P(n)
Powers of 2
f(0) =1, f(n+1) =2f(n)
aₙ = 2ⁿ
Fibonacci Sequence
f(n + 1) = 2f(n)
f₀ = 0, f₁ = 1
fₙ = fₙ₋₁ + fₙ₋₂, for n ≥ 2
Recursive Definition
aₙ = xⁿ for n = 0, 1, 2, 3, …
2
3
General form
n-th term
Sum
Recursive defiition
Sum
Recursive definition
Initial conditions
Sum of odd numbers
Explicit
1
5
6
Principle
Sum of 1 to n
General form
4
Recursive
n-th term