CSCE 222 Lecture 12

« previous | Wednesday, February 16, 2011 | next »

Summation

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=1}^n k = \frac{n(n+1)}{2}}

Example

for i in (1..n) do
  for j in (1..i) do
    # constant time
  end
end

How many times is the constant time function executed?

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1+2+3+\ldots+n) \Theta(1) = \frac{n(n+1)}{2} \Theta(1) = \Theta(n^2)}

Geometric Series

Let $r$ be any real number other than 0:

$\sum _{j=0}^{n}r^{j}=1+r+\ldots +r^{n}={\begin{cases}{\frac {r^{n+1}-1}{r-1}}&r\neq 1\\n+1&r=1\end{cases}}$

Let $r$ be a real number such that 0 < r < 1:

$\sum _{k=0}^{\infty }r^{k}={\frac {1}{1-r}}$

Products

$\prod _{k=m}^{n}a_{k}=a_{m}a_{m+1}\ldots a_{n}$

$\prod _{k=1}^{n}k=n!$

$\log \prod _{k=m}^{n}a_{k}=\sum _{k=m}^{n}\log {a_{k}}$

Proof by Induction

${\begin{array}{l}P(1)\\\forall n>1P(n-1)\rightarrow P(n)\\\hline \therefore \forall nP(n)\end{array}}$

Example

Claim:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}}

Proof: For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=1} , the left hand side is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{k=1}^1 k^2 = 1} and the right hand side is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1\cdot 2 \cdot 3}{6} = 1}

Suppose the claim holds for n-1. We are going to show that the claim holds for n:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{rcl} \sum_{k=1}^n k^2 &=& n^2 + \sum_{k=1}^{n-1} k^2 \\ &=& n^2 + \frac{(n-1)(n)(2(n-1)+1)}{6} \\ &=& n^2 + \frac{n(n-1)(2n-1)}{6} \\ &=& \frac{6n^2+(n^2-n)(2n-1)}{6} \\ &=& \frac{6n^2+n^2(2n-1)-2n^2+n}{6} \\ &=& \frac{n^2(2n+1)+2n^2+n}{6} \\ &=& \frac{(n^2+n)(2n+1)}{6} \\ &=& \frac{n(n+1)(2n+1)}{6} \quad \therefore P(n-1)\rightarrow P(n) \end{array}}

And therefore, the claim holds by induction on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} . ∎