CSCE 411 Lecture 4

Lecture Slides

« previous | Monday, September 3, 2012 | next »

Limit Superior

A tool used in Asymptotic Analysis.

The limit of a sequence might not exist:

$f(n)=1+(-1)^{n}\longrightarrow lim_{n\to \infty }f(n)=DNE$

Supremum

The supremum $b$ of a set of real numbers $S$ is the smallest real number $b$ such that $b\geq s$ for all $s$ in $S$

Notation: $b=\mathrm {sup} S$

• $\mathrm {sup} \left\{1,2,3\right\}=3$
• $\mathrm {sup} \left\{x~\mid ~x^{2}<2\right\}={\sqrt {2}}$
• $\mathrm {sup} \left\{(-1)^{n}-{\frac {1}{n}}~{\bigg |}~n\geq 0\right\}=1$

Limit Superior

The Limit superior of a sequence $x_{n}$ of real numbers is defined as

$\limsup _{n\to \infty }x_{n}=\lim _{n\to \infty }\left(\mathrm {sup} \left\{x_{m}~\mid ~m\geq n\right\}\right)$

Note: the limit superior always exists in the extended real line (including ±∞)

Asymptotic Applications

(complicated function of $n$) = (simple function of $n$) + (bound for size of error in terms of n)

For example, $1^{2}+2^{2}+3^{2}+\dots +n^{2}={\frac {n^{3}}{3}}+{\frac {n^{2}}{2}}+{\frac {n}{6}}={\frac {n^{3}}{3}}+O(n^{2})$

Bold Conjecture

$1^{k}+2^{k}+3^{k}+\dots +n^{k}={\frac {n^{k+1}}{k+1}}+O(n^{k})$

Proof. Estimate the sum $S(n)=1^{k}+2^{k}+3^{k}+\dots +n^{k}$ as an integral:

${\begin{aligned}S(n)&<\int _{1}^{n+1}x^{k}\,\mathrm {d} x={\frac {(n+1)^{k+1}}{k+1}}\\S(n)&>\int _{0}^{n}x^{k}\,\mathrm {d} x={\frac {n^{k+1}}{k}}\end{aligned}}$