in closed form. I claim that i=0 to n i2 = n(n+1)(2n+1)/6i=0 to n i2 = 
(n3).
First you would need to get the in closed form. I claim that
i=0 to n i2 = n(n+1)(2n+1)/6
First, this is easy to see since we have stated the from i=1 to n at our review page.
Now, if the only difference is that we also have the sum for when i is 0, well, that just means we add 02 to the sum. Big deal,
02 = 0, so the sum is the same. Nonetheless, in case the is not one you know, you should be familiar
with proofs by induction. So, here is the proof to remind you.
I will go over it on the review day.
Now we need to show that n(n+1)(2n+1)/6 =
Def. f(n) = O(g(n)) iff there exists positive constants c and no
such that f(n) < cg(n) for all n , n > no
Show that the following inequalities are correct:
iff
there exists positive constants c1, c2 and no
such that c1 n3 < (2n3 + 3n2 + n)/6 < c2 n3 for
all n , n > no
Let c1 = 1/6, c2 = 1, no = 1
1 < 2 + 3/n + 1/n2 is equal to 0 < 1 + 3/n + 1/n2 and is clearly true for all n , n > 1
DONE
Big Oh, Omega and Theta
So, we have i=0 to n i2 = n(n+1)(2n+1)/6 (n3). We will do this below
iff
there exists positive constants c1, c2 and no
such that c1g(n) < f(n) < c2g(n) for
all n , n > no
(n2)
Let c1 = 3, c2 = 5, no =
3
3n2 < 5n2 - 6n <
5n2
-2n2 < - 6n <
0 divide by negative changes direction of
inequality
0 < 3 < n for
all n , n > 3 DONE
i=0 to n i2 = (n3)
but
i=0 to n i2 = n(n+1)(2n+1)/6 so what we need to show is
n(n+1)(2n+1)/6 = (n3)n(n+1)(2n+1)/6 = (n2 + n)(2n + 1)/6 = (2n3 + n2 + 2n2 + n)/6 = (2n3 + 3n2 + n)/6
1/6*n3 < (2n3 + 3n2 + n)/6 < 1*n3 (times all through by 6)
1*n3 < 2n3 + 3n2 + n < 6*n3 (divide all through by n3)
1 < 2 + 3/n + 1/n2 < 6
2 + 3/n + 1/n2 < 6 is equal to 3/n + 1/n2 < 4 and is clearly true for all n , n > 1 since as n gets larger, the fractions get smallerNote that for proving inequalities do not hold, it is not
sufficient simply to find specific c's and n's that do not work since I may
be able to find a c or n that does. Hence, you need to show that
sooner or later any choice of c will have a problem. This is usually
done by considering the fact that the statement must be true "for all n, n
> n0"
Specifically, that n approaches infinity.
Suppose there is a c and no such that 10n2 + 9
< cn for all n , n > no
This would imply that
10n+9/n < c for all n , n > no
Or, more
specifically, that n < (c-9/n)/10 for all n , n >
no
But no matter what c or no one chooses, I can
always find an n > no to show this statement is incorrect
since c will be bound but n can grow infinitely and 9/n will approach 0.
Specifically, for any c, I could choose n = (c/10) + 1 and we have a
contradiction