Introduction to Probability

Multivariable Calculus

Algorithms: Part II

Algorithms: Part I

Introduction to Software Design and Architecture

Calculus Two: Sequences and Series

LAFF Linear Algebra

Stanford Machine Learning

Calculus One

Computational Thinking

Effective Thinking Through Mathematics

CS50 Introduction to Computer Science


Week 3 - Convergence Tests

Ratio Test


  • Does n54n\sum\frac{n^5}{4^n} convergence?
    • Use the Geometric Series Theory, we know that 14n\sum\frac{1}{4^n} convergence, because 14n=1414n1\sum\frac{1}{4^n} = \sum\frac{1}{4} \cdot {\frac{1}{4}^{n-1} } and 14<1\frac{1}{4} < 1.
    • Last week, we’ve learned Comparison Test Theory. So if we can find a series that every element in it is bigger than this one and also converges, then this example must converge, too.
    • Let’s calculate limnanan1\lim_{n \to \infty}\frac{a_n}{a_{n-1} }
      • limnanan1=limnn54n(n1)54n1=limnn54n4n1(n1)5=limn14(nn1)5=14\lim_{n \to \infty}\frac{a_n}{a_{n-1} } = \lim_{n \to \infty} \frac{\frac{n^5}{4^n} }{\frac{(n-1)^5}{4^{n-1} } } = \lim_{n \to \infty}\frac{n^5}{4^n} \cdot \frac{ 4^{ n-1 } }{ (n-1)^5 } = \lim_{n \to \infty}\frac{1}{4} (\frac{n}{n-1})^5 = \frac{1}{4}

      • So if n is big enough, then the common ratio will be close to 1/4.
    • Then we can pick a constant ϵ=0.1\epsilon = 0.1 that make anan1<14+0.1\vert \frac{a_n}{a_{n-1} } \vert < \frac{1}{4} + 0.1, after some calculation we got that n15n \ge 15.
      • So, an+1<(14+0.1)an, where n15a_{n+1} < (\frac{1}{4} + 0.1) a_n,\ \text{where}\ n \ge 15,
      • Then a15+k<(14+0.1)ka15a_{15+k} < (\frac{1}{4} + 0.1)^k a_{15}.
    • We know that (14+0.1)ka15\sum (\frac{1}{4} + 0.1)^k a_{15} convergence, base on the Geometric Series Theory.
    • So a15+k\sum a_{15+k} converge.
    • So ak\sum a_{k} converge.


  • Consider n=0an\displaystyle \sum_{n=0}^{\infty} a_n. And an0a_n \ge 0, limnan+1an=L\displaystyle \lim_{n \to \infty} \frac{a_{n+1} }{a_n} = L.
    • If L<1L < 1, then n=0an\displaystyle \sum_{n=0}^{\infty} a_n converges.
    • If L>1L > 1, then n=0an\displaystyle \sum_{n=0}^{\infty} a_n diverges.
    • If L=1L = 1, then the ratio test is inconclusive.


  • To find the series (n=1an, where an>0\sum_{n=1}^{\infty}a_n,\ \text{where}\ a_n > 0) converge or not.
  • If limnan+1an=L<1\lim_{n \to \infty}\frac{a_{n+1} }{a_n} = L < 1,
    • Then pick a small ϵ\epsilon so that L+ϵ<1L + \epsilon < 1
    • Find N so that nNn \ge N, an+1an<L+ϵ\frac{a_{n+1} }{a_n} < L + \epsilon.
    • Then aN+k<(L+ϵ)kaNa_{N+k} < (L+\epsilon)^k \cdot a_{N}
    • Since (L+ϵ)kaN\sum (L+\epsilon)^k \cdot a_{N} converge, aN+k\sum a_{N+k} converge.
    • So ak\sum a_{k} converge.
  • If limnan+1an=L>1\lim_{n \to \infty}\frac{a_{n+1} }{a_n} = L > 1,
    • Then pick a small ϵ\epsilon so that Lϵ>1L - \epsilon > 1
    • Find N so that nNn \ge N, an+1an>Lϵ\frac{a_{n+1} }{a_n} > L - \epsilon.
    • Then aN+k>(Lϵ)kaNa_{N+k} > (L-\epsilon)^k \cdot a_{N}
    • Since (L+ϵ)kaN\sum (L+\epsilon)^k \cdot a_{N} diverge, aN+k\sum a_{N+k} diverge.
    • So ak\sum a_{k} diverge.
  • If limnan+1an=L=1\lim_{n \to \infty}\frac{a_{n+1} }{a_n} = L = 1,
    • Might converge, like 1n2\sum \frac{1}{n^2}
    • Might diverge, like 1\sum 1

Other Examples

  • n!nn\sum \frac{n!}{n^n}, n!(n/2)n\sum \frac{n!}{(n/2)^n}, n!(n/3)n\sum \frac{n!}{(n/3)^n}
  • We know that e=limn(1+1n)ne = \displaystyle\lim_{n \to \infty} (1+\frac{1}{n})^n. With this, we can conclude n!(n/2)n\sum \frac{n!}{(n/2)^n} converges, n!(n/3)n\sum \frac{n!}{(n/3)^n} diverges.
  • But what about n!(n/e)n\sum \frac{n!}{(n/e)^n}. Let’s compare n!n! with nnn^n
    • log(n!)=k=1nlog(k)1nlogxdx=xlogxx]1n\log(n!) = \sum_{k=1}^n \log(k) \approx \int_1^n \log x dx = x \log x - x ]_1^n
    • log(n!)=nlognn+1\log(n!) = n \log n - n + 1
    • log(n!)nlognn=log(nnen)\log(n!) \approx n \log n - n = \log(\frac{n^n}{e^n})
    • n!(ne)nn! \approx (\frac{n}{e})^n
    • Better approximation is n!(ne)n2πnn! \approx (\frac{n}{e})^n \sqrt{2 \pi n}, which name is Stirling’s approximation.

Root Test


  • an>0,L=limnanna_n > 0, L = \displaystyle \lim_{n \to \infty} \sqrt[n]{a_n}
    • If L<1,n=1L < 1, \displaystyle \sum_{n=1}^{\infty} converge,
    • If L>1,n=1L > 1, \displaystyle \sum_{n=1}^{\infty} diverge,
    • If L=1,n=1L = 1, \displaystyle \sum_{n=1}^{\infty} inconclusive.

Integral Test


  • Suppose f is a continuous, positive, decreasing function on [1,)[1, \infty), and let an=f(n)a_n = f(n). Then the series n=1an\sum_{n=1}^{\infty} a_n is convergent if and only if the improper integral 1f(x)dx\int_{1}^{\infty} f(x) dx is convergent. In other words:
    • If 1f(x)dx\int_{1}^{\infty} f(x) dx is convergent, then n=1an\sum_{n=1}^{\infty} a_n is convergent.
    • If 1f(x)dx\int_{1}^{\infty} f(x) dx is divergent, then n=1an\sum_{n=1}^{\infty} a_n is divergent.

Proof of the Integral Test

  • For the general series an\sum a_n, look at the figures above. The area of the first shaded rectangle is the value of f at the right endpoint of [1, 2], that is, f(2)=a2f(2) = a_2. So, comparing the areas of the shaded rectangles with the area under y=f(x)y = f(x) from 1 to n, we see that
    • a2++an=sna1=i=2nai1nf(x)dxa1++an1=sn1i=1nai\displaystyle a_2 + \ldots + a_n = s_n - a_1 = \sum_{i=2}^n a_i \le \int_1^n f(x) dx \le a_1 + \ldots + a_{n-1} = s_{n-1} \le \sum_{i=1}^n a_i
      • Notice that this inequality depends on the fact that f is decreasing.
  • If 1nf(x)dx\int_1^n f(x) dx is convergent, then $$\sum_{i=2}^n a_i \le \int_1^n f(x) dx \le \int_1^{\infty} f(x) dx$$ since f(x)0f(x) \ge 0. Therefore $$s_n = a_1 + \sum_{i=2}^n a_i \le a_1 + \int_1^{\infty} f(x) dx$$
    • So the sequence {sn}\{s_n\} is bounded above.
    • And {sn}\{s_n\} is also an increasing sequence.
    • This means that an\sum a_n is convergence.
  • If 1nf(x)dx\int_1^n f(x) dx is divergent, then 1nf(x)dx as n\int_1^n f(x) dx \to \infty \ \text{as}\ n \to \infty because f(x)0f(x) \ge 0. But 1nf(x)dxi=1n1ai=sn1\displaystyle\int_1^n f(x) dx \le \sum_{i=1}^{n-1}a_i = s_{n-1} and so sn1s_{n-1} \to \infty. This implies that sns_n \to \infty and an\sum a_n diverges.


  • The Harmonic Series 1n\sum \frac{1}{n}
    • The Integral Test need the function is positive and decreasing on [1,)[1, \infty).
      • x1,f(x)>0x \ge 1, f(x) > 0
      • a>b,f(a)<f(b)a > b, f(a) < f(b)
    • Now let’s calculate 1f(x)d(x)\int_1^{\infty} f(x) d(x)
      • =limN1Nf(x)dx=limN1N1xdx= \displaystyle \lim_{N \to \infty} \int_1^N f(x) dx = \lim_{N \to \infty} \int_1^N \frac{1}{x} dx
      • =limN(logNlog1)=limNlogN= \displaystyle\lim_{N \to \infty} (\log N - \log 1) = \lim_{N \to \infty} \log N
      • == \infty
  • 1np\sum \frac{1}{n^p}
    • Method 1:
      • With Cauchy Condensation, we know that, n=11np\sum_{n=1}^{\infty} \frac{1}{n^p} converges if and only if n=02n1(2n)p\sum_{n=0}^{\infty} 2^n \frac{1}{(2^n)^p} converges.
      • n=02n1(2n)p=n=01(2n)p1=n=01(2p1)n\sum_{n=0}^{\infty} 2^n \frac{1}{(2^n)^p} = \sum_{n=0}^{\infty} \frac{1}{(2^n)^{p-1} } = \sum_{n=0}^{\infty} \frac{1}{(2^{p-1})^n }
      • Use the Geometric Series Theory, we got the ratio is 12p1\frac{1}{2^{p-1}}, so if p<1p < 1, it diverges; if p>1p > 1, it converges.
    • Method 2, use The Integral Test:
      • Let’s assume p1p \ne 1, which is The Harmonic Series we have proved before.
      • Also the function is positive and decreasing on [1,)[1, \infty), so we can use the Integral Test on this.
      • 1f(x)d(x)=limN1N1xpd(x)=limN(1p+1Np+11p+1)\displaystyle \int_1^{\infty} f(x) d(x) = \lim_{N \to \infty} \int_1^N \frac{1}{x^p} d(x) = \lim_{N \to \infty} (\frac{1}{-p+1} N^{-p+1} - \frac{1}{-p+1})
      • =limN1p+1(Np+11)\displaystyle = \lim_{N \to \infty} \frac{1}{-p+1} (N^{-p+1} - 1)
      • so if p<1p < 1, it diverges; if p>1p > 1, it converges.


  • factorial ['fæktɔ:riəl] adj. 因子的,阶乘的 n. [数] 阶乘