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+\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:

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

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