Exercise Lover

March 10, 2007

Exercises A.2-5

Filed under: A.2 — yuhanlyu @ 2:29 pm

Because \int^n_0 1/x dx when x = 0 is undefined value.

Exercises A.2-4

Filed under: A.2 — yuhanlyu @ 2:24 pm

\int^{n+1}_1 x^3 dx = (n+1)^4/4 - 1/4
\int^n_0 (x-1)^3 dx = n^4/4
\sum^n_{k=1} k^3 = \Theta(n^4)

Exercises A.2-3

Filed under: A.2 — yuhanlyu @ 2:19 pm

\sum^n_{k=1} 1/k
\geq \sum^{\lceil \lg n \rceil - 1}_{i=0} \sum^{2^i-1}_{j=0} 1/(2^i+j)
\geq \sum^{\lceil \lg n \rceil - 1}_{i=0} \sum^{2^i-1}_{j=0} 1/2^i
\geq \sum^{\lceil \lg n \rceil - 1}_{i=0} 1
= \Omega(\lg n)

Exercises A.2-2

Filed under: A.2 — yuhanlyu @ 7:54 am

\sum^{\lfloor \lg n \rfloor}_{k=1} \lceil n/2^k \rceil is obviously \Omega(n)
\sum^{\lfloor \lg n \rfloor}_{k=1} \lceil n/2^k \rceil
\leq \sum^{\lfloor \lg n \rfloor}_{k=1} n/2^k + 1
\leq n + \lg n
=O(n) Then
\sum^{\lfloor \lg n \rfloor}_{k=1} \lceil n/2^k \rceil = \Theta(n)

Exercises A.2-1

Filed under: A.2 — yuhanlyu @ 7:50 am

\sum^n_{k=1} 1/k^2
\leq 1+ \sum^n_{k=2} 1/k(k-1)
= 1 + \sum^n_{k=2} 1/(k-1) - 1/k
= 1 + 1 - 1/n
< 2

Indeed, \sum^{\infty}_{k=1} 1/k^2 = {\pi}^2/6

Blog at WordPress.com.