3.2

Exercises 3.2-1

---

Show that if f(n) and g(n) are monotonically increasing functions, then so are the functions f(n) + g(n) and f (g(n)), and if f(n) and g(n) are in addition nonnegative, then f(n) · g(n) is monotonically increasing.

Answer

Given that f(n) and g(n) are monotonically increasing functions, So
f(n) <= f(n+1)         (1)
g(n) <= g(n+1)         (2)
Adding eqn. (1) and (2), we get
f(n) + g(n) <= f(n+1) + g(n+1)
Therefore f(n) + g(n) is monotonically increasing function.
Since, g(n) <= g(n+1) and f(n) is a monotonically increasing function.
So, f(g(n)) <= f(g(n+1))
Therefore f(g(n)) is a monotonically increasing function.
Given f(n) >=0 and g(n) >= 0
Then multiplying eqn. (1) and (2) results into
f(n) · g(n) <= f(n+1) · g(n+1)
Therefore f(n) · g(n) is monotonically increasing.

Exercises 3.2-2

---

Prove equation (3.15).

Answer

Exercises 3.2-3

---

Prove equation (3.18). Also prove that n! = ω(2^n) and n! = o(n^n).

Answer

采用暴力方法，直接证明极限在一个常数区间内

Exercises 3.2-4

---

Is the function polynomially bounded? Is the function polynomially bounded?

Answer

多项式边界也就是函数

两边取对数得到

所以，如果一个函数f(n)是有多项式边界，就满足

令

令

Exercises 3.2-5

---

Which is asymptotically larger: lg(lg n)* or *lg(lg n)**?

Answer

第2个大. Suppose log star of n is k, then the first one is log(k) while the second one is k - 1.

...表示多重对数函数的逆操作

Exercises 3.2-6

---

Prove by induction that the ith Fibonacci number satisfies the equality

Answer

Exercises 3.2-7

---

Prove that for i ≥ 0, the (i + 2)nd Fibonacci number satisfies Fi+2 ≥ φi.

Answer

---

Follow @louis1992 on github to help finish this task.