Sequence: An ordered list of numbers \(\{a_1, a_2, a_3, \ldots\}\)
Explicit formula: Formula expressing \(a_n\) directly in terms of \(n\)
Convergence: A sequence converges if \(\lim_{n \to \infty} a_n\) exists and is finite
- Substitute values of n into the explicit formula
- Calculate each term individually
- Find the limit as n approaches infinity
- Determine convergence based on limit existence
\(a_1 = \frac{1^2 + 1}{2(1) - 1} = \frac{1 + 1}{2 - 1} = \frac{2}{1} = 2\)
\(a_2 = \frac{2^2 + 1}{2(2) - 1} = \frac{4 + 1}{4 - 1} = \frac{5}{3}\)
\(a_3 = \frac{3^2 + 1}{2(3) - 1} = \frac{9 + 1}{6 - 1} = \frac{10}{5} = 2\)
\(a_4 = \frac{4^2 + 1}{2(4) - 1} = \frac{16 + 1}{8 - 1} = \frac{17}{7}\)
\(a_5 = \frac{5^2 + 1}{2(5) - 1} = \frac{25 + 1}{10 - 1} = \frac{26}{9}\)
\(a_6 = \frac{6^2 + 1}{2(6) - 1} = \frac{36 + 1}{12 - 1} = \frac{37}{11}\)
\(\lim_{n \to \infty} \frac{n^2 + 1}{2n - 1}\)
Divide numerator and denominator by highest power of n (which is n):
\(\lim_{n \to \infty} \frac{n + \frac{1}{n}}{2 - \frac{1}{n}} = \lim_{n \to \infty} \frac{n}{2} = \infty\)
Sequence diverges to infinity
First 6 terms: \(a_1 = 2\), \(a_2 = \frac{5}{3}\), \(a_3 = 2\), \(a_4 = \frac{17}{7}\), \(a_5 = \frac{26}{9}\), \(a_6 = \frac{37}{11}\)
The sequence diverges to infinity.
• Direct substitution: Plug in values of n to find specific terms
• Limits of rational functions: Divide by highest power of n
• Convergence criterion: Sequence converges if limit exists and is finite
Recursive relation: Formula defining each term based on previous terms
Initial condition: Starting value(s) for the recursion
\(a_1 = 1\)
\(a_2 = \frac{a_1}{2} + \frac{1}{a_1} = \frac{1}{2} + \frac{1}{1} = \frac{1}{2} + 1 = \frac{3}{2} = 1.5\)
\(a_3 = \frac{a_2}{2} + \frac{1}{a_2} = \frac{3/2}{2} + \frac{1}{3/2} = \frac{3}{4} + \frac{2}{3} = \frac{9 + 8}{12} = \frac{17}{12} \approx 1.417\)
\(a_4 = \frac{a_3}{2} + \frac{1}{a_3} = \frac{17/12}{2} + \frac{1}{17/12} = \frac{17}{24} + \frac{12}{17} = \frac{289 + 288}{408} = \frac{577}{408} \approx 1.414\)
\(a_5 = \frac{a_4}{2} + \frac{1}{a_4} = \frac{577/408}{2} + \frac{1}{577/408} = \frac{577}{816} + \frac{408}{577} \approx 1.414\)
This sequence appears to be approaching \(\sqrt{2} \approx 1.414\)
Notice that this is Newton's method for finding \(\sqrt{2}\)
Limit: \(\sqrt{2}\)
First 5 terms: \(a_1 = 1\), \(a_2 = 1.5\), \(a_3 \approx 1.417\), \(a_4 \approx 1.414\), \(a_5 \approx 1.414\)
The sequence converges to \(\sqrt{2}\).
• Recursive substitution: Use previous term to calculate next term
• Newton's method: This recurrence relation is Newton's method for \(\sqrt{2}\)
• Pattern recognition: Look for convergence behavior in calculated terms
Bounded sequence: A sequence is bounded if there exists M > 0 such that \(|a_n| \leq M\) for all n
Since \(|\sin(n)| \leq 1\) for all n, we have:
\(|a_n| = \left|\frac{\sin(n)}{n}\right| = \frac{|\sin(n)|}{n} \leq \frac{1}{n}\)
For all \(n \geq 1\), \(\frac{1}{n} \leq 1\), so \(|a_n| \leq 1\)
Therefore, the sequence is bounded by M = 1.
We want to find \(\lim_{n \to \infty} \frac{\sin(n)}{n}\)
Since \(-1 \leq \sin(n) \leq 1\), we have:
\(\frac{-1}{n} \leq \frac{\sin(n)}{n} \leq \frac{1}{n}\)
\(\lim_{n \to \infty} \frac{-1}{n} = 0\) and \(\lim_{n \to \infty} \frac{1}{n} = 0\)
By the Squeeze Theorem: \(\lim_{n \to \infty} \frac{\sin(n)}{n} = 0\)
The sequence is bounded and converges to 0.
This demonstrates that oscillating functions divided by growing functions tend to 0.
Bounded by 1
The sequence \(a_n = \frac{\sin(n)}{n}\) converges to 0.
The sequence is bounded since \(|a_n| \leq 1\) for all n.
• Squeeze Theorem: If \(a_n \leq b_n \leq c_n\) and \(\lim a_n = \lim c_n = L\), then \(\lim b_n = L\)
• Boundedness test: Show \(|a_n| \leq M\) for some positive constant M
• Oscillating functions: \(\frac{\sin(n)}{n} \to 0\) as \(n \to \infty\)
Sequence: A function whose domain is the set of positive integers
Explicit formula: Direct formula \(a_n = f(n)\) to compute any term
Recursive formula: Defines each term based on previous terms
Convergence: A sequence converges if \(\lim_{n \to \infty} a_n\) exists and is finite
Divergence: A sequence diverges if the limit does not exist or is infinite
Bounded sequence: There exists M > 0 such that \(|a_n| \leq M\) for all n
Monotonic sequence: Either always increasing or always decreasing
- Identify sequence type: Explicit or recursive formula
- Calculate initial terms: Understand pattern and behavior
- Determine convergence: Find limit if it exists
- Test boundedness: Check if terms stay within bounds
- Apply convergence tests: Use appropriate theorems and criteria
• Squeeze Theorem: If \(a_n \leq b_n \leq c_n\) and \(\lim a_n = \lim c_n = L\), then \(\lim b_n = L\)
• Bounded Monotonic Sequence Theorem: Every bounded monotonic sequence converges
• Limit Properties: \(\lim(ca_n) = c\lim(a_n)\), \(\lim(a_n + b_n) = \lim a_n + \lim b_n\)
• Ratio Test for Sequences: If \(\lim|\frac{a_{n+1}}{a_n}| < 1\), then \(\lim a_n = 0\)
• Root Test for Sequences: If \(\lim\sqrt[n]{|a_n|} < 1\), then \(\lim a_n = 0\)
Monotonic increasing: \(a_{n+1} \geq a_n\) for all n
Compare consecutive terms: \(a_{n+1} - a_n\)
\(a_{n+1} = \frac{n+1}{(n+1)+1} = \frac{n+1}{n+2}\)
\(a_{n+1} - a_n = \frac{n+1}{n+2} - \frac{n}{n+1}\)
\(= \frac{(n+1)^2 - n(n+2)}{(n+1)(n+2)} = \frac{n^2 + 2n + 1 - n^2 - 2n}{(n+1)(n+2)} = \frac{1}{(n+1)(n+2)} > 0\)
Since \(a_{n+1} - a_n > 0\), the sequence is increasing.
Notice that \(a_n = \frac{n}{n+1} = \frac{n+1-1}{n+1} = 1 - \frac{1}{n+1}\)
Since \(\frac{1}{n+1} > 0\) for all \(n \geq 1\), we have \(a_n = 1 - \frac{1}{n+1} < 1\)
Also, since \(\frac{1}{n+1} \leq 1\) for \(n \geq 1\), we have \(a_n = 1 - \frac{1}{n+1} \geq 0\)
Therefore, \(0 \leq a_n < 1\) for all n, so the sequence is bounded.
\(\lim_{n \to \infty} \frac{n}{n+1}\)
Divide numerator and denominator by n:
\(\lim_{n \to \infty} \frac{1}{1 + \frac{1}{n}} = \frac{1}{1 + 0} = 1\)
Since the sequence is monotonic increasing and bounded above, by the Bounded Monotonic Sequence Theorem, it converges.
The limit is 1.
Bounded: [0, 1)
Limit: 1
The sequence \(a_n = \frac{n}{n+1}\) is monotonic increasing and bounded.
The sequence converges to 1.
• Monotonicity test: Compare consecutive terms to determine increasing/decreasing
• Bounded Monotonic Sequence Theorem: Bounded monotonic sequences converge
• Algebraic manipulation: Rewrite expressions to reveal properties
Factorial growth: \(n!\) grows faster than exponential functions
Use the ratio test for sequences: \(\lim_{n \to \infty} \left|\frac{a_{n+1}}{a_n}\right|\)
\(\frac{a_{n+1}}{a_n} = \frac{3^{n+1}/(n+1)!}{3^n/n!} = \frac{3^{n+1}}{(n+1)!} \cdot \frac{n!}{3^n} = \frac{3}{n+1}\)
\(\lim_{n \to \infty} \frac{3}{n+1} = 0 < 1\)
Therefore, \(\lim_{n \to \infty} a_n = 0\)
Use Stirling's approximation: \(n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n\)
So \(b_n = \frac{n!}{n^n} \approx \frac{\sqrt{2\pi n} \left(\frac{n}{e}\right)^n}{n^n} = \sqrt{2\pi n} \cdot \frac{1}{e^n}\)
As \(n \to \infty\), \(\frac{\sqrt{2\pi n}}{e^n} \to 0\) (exponential dominates polynomial)
Therefore, \(\lim_{n \to \infty} b_n = 0\)
We can also write: \(b_n = \frac{n!}{n^n} = \frac{1 \cdot 2 \cdot 3 \cdots n}{n \cdot n \cdot n \cdots n} = \frac{1}{n} \cdot \frac{2}{n} \cdot \frac{3}{n} \cdots \frac{n}{n}\)
Each factor \(\frac{k}{n} \leq 1\) for \(k \leq n\), and many factors are much less than 1
For large n, the product approaches 0
Both sequences converge to 0, but factorial grows faster than exponential
This demonstrates that \(n!\) grows faster than any exponential function \(a^n\)
\(b_n = \frac{n!}{n^n} \to 0\)
Factorial grows faster than exponentials
Both sequences converge to 0: \(\lim_{n \to \infty} \frac{3^n}{n!} = 0\) and \(\lim_{n \to \infty} \frac{n!}{n^n} = 0\)
This illustrates that factorial functions grow faster than exponential functions.
• Ratio test for sequences: If \(\lim|\frac{a_{n+1}}{a_n}| < 1\), then \(\lim a_n = 0\)
• Stirling's approximation: \(n! \approx \sqrt{2\pi n}(n/e)^n\)
• Growth rate comparison: \(n! > a^n > n^p > \ln(n)\) for large n
Subsequence: A sequence formed by selecting terms from the original sequence
Cauchy sequence: A sequence where terms get arbitrarily close together
Accumulation point: A number that is the limit of some subsequence
Lim sup and lim inf: Limit superior and inferior of a sequence
Asymptotic equivalence: \(a_n \sim b_n\) if \(\lim \frac{a_n}{b_n} = 1\)
- Comparison tests: Compare with known convergent/divergent sequences
- Ratio/root tests: For sequences involving factorials or exponentials
- Stolz-Cesàro theorem: Discrete version of L'Hôpital's rule
- Generating functions: Transform sequences into functions
- Asymptotic analysis: Study behavior using approximations
• Stolz-Cesàro Theorem: If \(\lim \frac{a_{n+1}-a_n}{b_{n+1}-b_n} = L\) and \(b_n\) is strictly monotonic, then \(\lim \frac{a_n}{b_n} = L\)
• Bolzano-Weierstrass Theorem: Every bounded sequence has a convergent subsequence
• Cauchy Criterion: A sequence converges iff it is Cauchy
• Dominance Relations: \(n! \gg a^n \gg n^p \gg \ln(n) \gg 1\) as \(n \to \infty\)
• Binet Formula: For Fibonacci: \(F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}\) where \(\phi = \frac{1+\sqrt{5}}{2}\)
Questions & Answers
Question: What's the difference between a sequence and a series? I often confuse them.
Answer: This is a common source of confusion:
- Sequence: An ordered list of numbers \(\{a_1, a_2, a_3, \ldots\}\). We study whether it converges to a limit.
- Series: The sum of a sequence \(\sum_{n=1}^{\infty} a_n = a_1 + a_2 + a_3 + \cdots\). We study whether this sum converges to a finite value.
Think of it this way:
- A sequence is like a list of individual numbers: \(1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \ldots\)
- A series is like adding those numbers together: \(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots\)
Sequences come first conceptually - they form the building blocks for series. A series is essentially the sequence of partial sums.
Question: How do I determine if a sequence converges or diverges? What are the key tests?
Answer: Here are the main approaches to determine convergence:
- Direct computation: Try to find \(\lim_{n \to \infty} a_n\) directly
- Squeeze theorem: Bound the sequence between two converging sequences
- Monotonic sequence theorem: If bounded and monotonic, it converges
- Ratio test for sequences: If \(\lim|\frac{a_{n+1}}{a_n}| < 1\), then \(\lim a_n = 0\)
For divergence, look for:
- Limit goes to infinity: \(\lim a_n = \pm\infty\)
- Oscillation without settling: like \((-1)^n\)
- Terms that grow without bound
Always check if the sequence is bounded first - if not, it diverges.
Question: What does it mean for a sequence to be monotonic? How do I prove monotonicity?
Answer: A sequence is monotonic if it's either always increasing or always decreasing:
- Monotonic increasing: \(a_{n+1} \geq a_n\) for all n (or \(a_{n+1} > a_n\) for strictly increasing)
- Monotonic decreasing: \(a_{n+1} \leq a_n\) for all n (or \(a_{n+1} < a_n\) for strictly decreasing)
To prove monotonicity:
- Direct comparison: Show \(a_{n+1} - a_n \geq 0\) (or \(\leq 0\))
- Ratio test: Show \(\frac{a_{n+1}}{a_n} \geq 1\) (or \(\leq 1\)) for positive sequences
- Function approach: If \(a_n = f(n)\), analyze \(f'(x)\) for \(x \geq 1\)
Monotonic sequences that are also bounded are guaranteed to converge!
Question: How do factorials and exponentials compare in growth rate? Why does \(n!/a^n \to 0\)?
Answer: The growth rate hierarchy is: \(n! \gg a^n \gg n^p \gg \ln(n) \gg 1\)
To prove \(n!/a^n \to 0\), use the ratio test:
\(\frac{(n+1)!/a^{n+1}}{n!/a^n} = \frac{(n+1)!}{n!} \cdot \frac{a^n}{a^{n+1}} = \frac{n+1}{a}\)
For any fixed \(a > 0\), \(\frac{n+1}{a} \to \infty\) as \(n \to \infty\)
Wait, that's not right! Actually, for \(n!/a^n\), we get:
\(\frac{a_{n+1}}{a_n} = \frac{(n+1)!/a^{n+1}}{n!/a^n} = \frac{n+1}{a}\)
This ratio goes to infinity, suggesting divergence. However, we need to be more careful.
Actually, for the sequence \(a_n = a^n/n!\), the ratio is \(\frac{a}{n+1} \to 0\), so \(a^n/n! \to 0\).
Thus \(n!/a^n \to \infty\), confirming that factorials grow faster than exponentials.
Question: How do these sequence concepts apply to computer science and algorithm analysis?
Answer: Sequences are fundamental to algorithm analysis:
- Time complexity: Running times form sequences (e.g., \(T(n) = n^2\))
- Space complexity: Memory usage as a sequence of values
- Iterative algorithms: Convergence of iterative methods
- Data structures: Growth of tree heights, hash table collisions
For example, binary search has sequence of comparisons: \(\log_2(n)\) which grows much slower than linear search's \(n\).
Understanding sequence growth helps choose optimal algorithms: quicksort's \(O(n \log n)\) vs bubble sort's \(O(n^2)\).
Recursive algorithms naturally lead to recursive sequences for analysis.