CSCE 222 Lecture 12

From Notes
Jump to navigation Jump to search

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


Summation

∑k=1nk=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+…+n)Θ(1)=n(n+1)2Θ(1)=Θ(n2)

Geometric Series

Let r be any real number other than 0:

∑j=0nrj=1+r+…+rn={rn+1−1r−1r≠1n+1r=1

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

∑k=0∞rk=11−r


Products

∏k=mnak=amam+1…an

∏k=1nk=n!

log⁡∏k=mnak=∑k=mnlog⁡ak


Proof by Induction

P(1)∀n>1P(n−1)→P(n)∴∀nP(n)

Example

Claim:

∑k=1nk2=n(n+1)(2n+1)6

Proof: For n=1, the left hand side is ∑k=11k2=1 and the right hand side is 1⋅2⋅36=1

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

∑k=1nk2=n2+∑k=1n−1k2=n2+(n−1)(n)(2(n−1)+1)6=n2+n(n−1)(2n−1)6=6n2+(n2−n)(2n−1)6=6n2+n2(2n−1)−2n2+n6=n2(2n+1)+2n2+n6=(n2+n)(2n+1)6=n(n+1)(2n+1)6∴P(n−1)→P(n)

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