Recursively defined sequences
Sequences in which each term is computed from the previous one by a function f: first terms, cobweb plot, fixed point, arithmetico-geometric sequences reduced to a geometric one, and order-2 recurrences such as Fibonacci.
- 25 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- Scenarios
- Understand
A few cards from the deck
Recurrence relation: what is it?
Show the answer
An equality that expresses each term of a sequence from the term or terms before it; it only fixes the sequence once its first terms are given.
uₙ₊₁ = 2uₙ + 3 says nothing until u₀ is given: with u₀ = 0 you get 3, 9, 21; with u₀ = 1 you get 5, 13, 29.
What does this program print?
```python
u = 1
for _ in range(3):
u = 2 * u + 3
print(u)`2913618
Show the answer
29The three rounds give 5, 13, 29: this is u₃. Two rounds stop at 13, four rounds reach 61, and 8 forgets the “+ 3” in each round.
If the sequence uₙ₊₁ = f(uₙ) converges to ℓ and f is …, then ℓ satisfies ….
Show the answer
If the sequence uₙ₊₁ = f(uₙ) converges to ℓ and f is continuous, then ℓ satisfies f(ℓ) = ℓ.
Take the limit in uₙ₊₁ = f(uₙ): continuity lets you write lim f(uₙ) = f(ℓ). The converse is false: a fixed point is not always a limit.
Recursively defined sequence: what is it?
Show the answer
A sequence given by its first term u₀ and a function f that produces each term from the previous one: uₙ₊₁ = f(uₙ).
To reach u₁₀₀ from u₀ you must compute u₁, u₂, …, u₉₉ one by one, unless you find an explicit formula in n.
The sequence satisfies uₙ₊₁ = 0.8uₙ + 6. Which auxiliary sequence is geometric?
- vₙ = uₙ − 6, with ratio 0.8
- vₙ = uₙ + 30, with ratio 0.8
- vₙ = uₙ − 30, with ratio 0.2
- vₙ = uₙ − 30, with ratio 0.8
Show the answer
vₙ = uₙ − 30, with ratio 0.8
The fixed point is ℓ = 6 / (1 − 0.8) = 30. Then uₙ₊₁ − 30 = 0.8uₙ + 6 − 30 = 0.8(uₙ − 30). You subtract the fixed point, not the constant 6, and the ratio stays 0.8.