CSCE 222 Lecture 12

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

Summation

$\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?

$(1+2+3+\dots +n)\mathrm{\Theta }(1)=\frac{n(n+1)}{2}\mathrm{\Theta }(1)=\mathrm{\Theta }(n^2)$

Geometric Series

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

$\sum _{j=0}^n{r}^j=1+r+\dots +r^n=\{\begin{array}{ll}\frac{r^{n+1}-1}{r-1}& r\ne 1\\ n+1& r=1\end{array}$

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

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

Products

$\prod _{k=m}^n{a}_k=a_m{a}_{m+1}\dots 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)\\ \mathrm{\forall }n>1P(n-1)\to P(n)\\ \therefore \mathrm{\forall }nP(n)\end{array}$

Example

Claim:

$\sum _{k=1}^n{k}^2=\frac{n(n+1)(2n+1)}{6}$

Proof: For $n=1$, the left hand side is $\sum _{k=1}^1{k}^2=1$ and the right hand side is $\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:

$\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}\therefore P(n-1)\to P(n)\end{array}$

And therefore, the claim holds by induction on $n$. ∎