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 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 r} be any real number other than 0:

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_{j=0}^n r^j = 1+r+\ldots+r^n = \begin{cases} \frac{r^{n+1}-1}{r-1} & r\ne 1 \\ n+1 & r=1\end{cases}}

Let 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 r} be a real number such that 0 < r < 1:

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=0}^\infty r^k = \frac{1}{1-r}}

Products

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 \prod_{k=m}^n a_k = a_m a_{m+1} \ldots a_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 \prod_{k=1}^n k = 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 \log \prod_{k=m}^n a_k = \sum_{k=m}^n \log{a_k}}

Proof by Induction

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}{l} P(1) \\ \forall n>1 P(n-1) \rightarrow P(n) \\ \hline \therefore \forall n P(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} . ∎