隨手做的，可能沒有很完整，有看到有趣的題目或是重要的定理或是我想記錄才會放上來。
Sequences
Limit of a Sequence
lim n → ∞ a n = L ⟺ ∀ ϵ > 0 , ∃ N s . t . ∀ n > N , ∣ a n − L ∣ < ϵ \lim_{n \to \infty} a_n = L \iff \forall \epsilon > 0, \exists N \ s.t.\ \forall n > N, |a_n - L| < \epsilon n → ∞ lim a n = L ⟺ ∀ ϵ > 0 , ∃ N s . t . ∀ n > N , ∣ a n − L ∣ < ϵ lim n → ∞ a n = ∞ ⟺ ∀ M > 0 , ∃ N s . t . ∀ n > N , a n > M \lim_{n \to \infty} a_n = \infty \iff \forall M > 0, \exists N \ s.t.\ \forall n > N, a_n > M n → ∞ lim a n = ∞ ⟺ ∀ M > 0 , ∃ N s . t . ∀ n > N , a n > M Discrete v.s. Continuous
lim x → ∞ f ( x ) = L , f ( n ) = a n ∀ n ∈ Z + ⟹ lim n → ∞ a n = L \lim_{x \to \infty} f(x) = L, f(n) = a_n \ \forall n \in \mathbb{Z}^+ \implies \lim_{n \to \infty} a_n = L x → ∞ lim f ( x ) = L , f ( n ) = a n ∀ n ∈ Z + ⟹ n → ∞ lim a n = L Limit + Continuous Function
If lim n → ∞ a n = L \lim_{n \to \infty} a_n = L lim n → ∞ a n = L f f f continuous at L L L , then lim n → ∞ f ( a n ) = f ( lim n → ∞ a n ) = f ( L ) \lim_{n \to \infty} f(a_n) = f(\lim_{n \to \infty} a_n) = f(L) lim n → ∞ f ( a n ) = f ( lim n → ∞ a n ) = f ( L )
Monotonic / Bounded
Increasing: a n < a n + 1 a_n < a_{n+1} a n < a n + 1
Decreasing: a n > a n + 1 a_n > a_{n+1} a n > a n + 1
Monotonic: Either Increasing or Decreasing
Bounded Above (上面有東西擋住): ∃ M s . t . a n ≤ M ( ∀ n ) \exists M \ s.t.\ a_n \leq M \ (\forall n) ∃ M s . t . a n ≤ M ( ∀ n )
Bounded Below (下面有東西擋住): ∃ m s . t . m ≤ a n ( ∀ n ) \exists m \ s.t.\ m \leq a_n \ (\forall n) ∃ m s . t . m ≤ a n ( ∀ n )
Bounded Sequence: bounded above and below at the same time
Monotonic Sequence Theorem
Increasing and Bounded Above ⟹ \implies ⟹ Decreasing and Bounded Below ⟹ \implies ⟹
證明：由 LUB 公理得出存在最小上界 L L L
Monotonic Sequence Theorem 很常出現在後續章節的定理證明，包括 Intergral Test、Comparison Test、Alternating Series Test (Even Partial Sum 收斂的證明)。
Series
Convergence Tests for Series
∑ n = 1 ∞ a n is convergent ⟹ lim n → ∞ a n = 0 \sum_{n=1}^\infty a_n \text{ is convergent} \implies \lim_{n \to \infty} a_n = 0 n = 1 ∑ ∞ a n is convergent ⟹ n → ∞ lim a n = 0 lim n → ∞ a n ≠ 0 ⟹ ∑ n = 1 ∞ a n is divergent \lim_{n \to \infty} a_n \neq 0 \implies \sum_{n=1}^\infty a_n \text{ is divergent} n → ∞ lim a n = 0 ⟹ n = 1 ∑ ∞ a n is divergent
lim n → ∞ a n = 0 ⇏ ∑ n = 1 ∞ a n is convergent (Counter Example: ∑ n = 1 ∞ 1 n ) \displaystyle \lim_{n \to \infty} a_n = 0 \nRightarrow \sum_{n=1}^\infty a_n \text{ is convergent (Counter Example: } \sum_{n=1}^\infty \frac{1}{n}) n → ∞ lim a n = 0 ⇏ n = 1 ∑ ∞ a n is convergent (Counter Example: n = 1 ∑ ∞ n 1 )
∑ n = 1 ∞ 1 n p ( ln n ) q is convergent if p > 1 or p = 1 , q > 1 \sum_{n=1}^\infty \frac{1}{n^p(\ln n)^q} \text{ is convergent if } p > 1 \text{ or } p = 1, q > 1 n = 1 ∑ ∞ n p ( ln n ) q 1 is convergent if p > 1 or p = 1 , q > 1 ∑ n = 1 ∞ 1 n p ( ln n ) q is divergent if p < 1 or p = 1 , q ≤ 1 \sum_{n=1}^\infty \frac{1}{n^p(\ln n)^q} \text{ is divergent if } p < 1 \text{ or } p = 1, q \leq 1 n = 1 ∑ ∞ n p ( ln n ) q 1 is divergent if p < 1 or p = 1 , q ≤ 1 幾何級數就看公比: ∣ r ∣ < 1 |r| < 1 ∣ r ∣ < 1
使用條件：
a n a_n a n a n a_n a n 遞減 ，可用 f ′ ( x ) f'(x) f ′ ( x )
∑ n = 1 ∞ a n \sum_{n=1}^\infty a_n ∑ n = 1 ∞ a n ∫ 1 ∞ f ( x ) d x \int_1^\infty f(x)dx ∫ 1 ∞ f ( x ) d x
證明：
收斂的部分用 DCT + MST 證：
發散的部分用 DCT 證：
數論裡面一些演算法的時間複雜度、函數成長速度就是用積分估算的。
調和級數：∑ n = 1 N N n ≈ ∫ 1 N N x d x = Θ ( N log N ) \displaystyle \sum_{n=1}^N \frac{N}{n} \approx \int_1^N \frac{N}{x} dx = \Theta(N \log N) n = 1 ∑ N n N ≈ ∫ 1 N x N d x = Θ ( N log N )
杜教篩：N 2 3 + ∑ n = 1 ⌊ N 1 / 3 ⌋ N n ≈ N 2 3 + ∫ 1 N 1 / 3 N x d x = O ( N 2 3 ) \displaystyle N^{\frac{2}{3}} + \sum_{n=1}^{\lfloor N^{1/3} \rfloor} \sqrt{\frac{N}{n}} \approx N^{\frac{2}{3}} + \int_1^{N^{1/3}} \sqrt{\frac{N}{x}} dx = O(N^{\frac{2}{3}}) N 3 2 + n = 1 ∑ ⌊ N 1/3 ⌋ n N ≈ N 3 2 + ∫ 1 N 1/3 x N d x = O ( N 3 2 )
使用條件：
a n a_n a n
有分成 DCT 跟 LCT，但形式都滿單純的所以就不寫上來。
DCT 證明可以用 MST，而 LCT 證明可以先設 m < a n / b n < M ⟹ m b n < a n < M b n m < a_n / b_n < M \implies m b_n < a_n < M b_n m < a n / b n < M ⟹ m b n < a n < M b n
(5) Alternating Series Test
以下兩個條件都要驗證，注意不能只驗證第 2 個：
∣ a n ∣ |a_n| ∣ a n ∣ ∣ a n ∣ − ∣ a n + 1 ∣ ≥ 0 |a_n| - |a_{n+1}| \geq 0 ∣ a n ∣ − ∣ a n + 1 ∣ ≥ 0 lim n → ∞ ∣ a n ∣ = 0 \lim_{n \to \infty} |a_n| = 0 lim n → ∞ ∣ a n ∣ = 0
其實把 s n s_n s n s n s_n s n
證明的話也很單純，以最後收斂的和 s s s
Ratio Test: Let r = lim n → ∞ ∣ a n + 1 a n ∣ r = \lim_{n \to \infty} \left| \frac{a_{n+1}}{a_n} \right| r = lim n → ∞ a n a n + 1
Root Test: Let r = lim n → ∞ ∣ a n ∣ n r = \lim_{n \to \infty} \sqrt[n]{\vert a_n \vert} r = lim n → ∞ n ∣ a n ∣
If r < 1 ⟹ r < 1 \implies r < 1 ⟹
If r > 1 ∨ r = ∞ ⟹ r > 1 \lor r = \infty \implies r > 1 ∨ r = ∞ ⟹
If r = 1 ⟹ r = 1 \implies r = 1 ⟹
事實上兩個 Test 等價，即：
lim n → ∞ ∣ a n + 1 a n ∣ = r ⟺ lim n → ∞ ∣ a n ∣ n = r (Cauchy’s Second Theorem on Limits) \lim_{n \to \infty} \left| \frac{a_{n+1}}{a_n} \right| = r \iff \lim_{n \to \infty} \sqrt[n]{\vert a_n \vert} = r \quad \text{(Cauchy's Second Theorem on Limits)} n → ∞ lim a n a n + 1 = r ⟺ n → ∞ lim n ∣ a n ∣ = r (Cauchy’s Second Theorem on Limits) 餘項估計
定義 s s s ∑ a n \sum a_n ∑ a n
定義 R n = s − s n = ∑ k = n + 1 ∞ a k R_n = s - s_n = \sum_{k=n+1}^\infty a_k R n = s − s n = ∑ k = n + 1 ∞ a k
有時候級數和沒有特定公式可以計算，只能取前面有限個項，餘項估計就是在考慮只取有限個項的情況下產生的誤差。
Integral Test
∫ n + 1 ∞ f ( x ) d x ≤ R n ≤ ∫ n ∞ f ( x ) d x \int_{n+1}^\infty f(x)dx \leq R_n \leq \int_n^\infty f(x)dx ∫ n + 1 ∞ f ( x ) d x ≤ R n ≤ ∫ n ∞ f ( x ) d x s n + ∫ n + 1 ∞ f ( x ) d x ≤ s ≤ s n + ∫ n ∞ f ( x ) d x s_n + \int_{n+1}^\infty f(x)dx \leq s \leq s_n + \int_n^\infty f(x)dx s n + ∫ n + 1 ∞ f ( x ) d x ≤ s ≤ s n + ∫ n ∞ f ( x ) d x Alternating Series Test
∣ R n ∣ ≤ ∣ a n + 1 ∣ |R_n| \leq |a_{n+1}| ∣ R n ∣ ≤ ∣ a n + 1 ∣
