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.
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.
Prove equation (3.15).
Prove equation (3.18). Also prove that n! = ω(2^n) and n! = o(n^n).
采用暴力方法，直接证明极限在一个常数区间内
Is the function polynomially bounded? Is the function
polynomially bounded?
多项式边界也就是函数
两边取对数得到
所以，如果一个函数f(n)是有多项式边界，就满足
令
令
Which is asymptotically larger: lg(lg n)* or lg(lg n)*?
第2个大. Suppose log star of n is k, then the first one is log(k) while the second one is k - 1.
...表示多重对数函数的逆操作
Prove by induction that the ith Fibonacci number satisfies the equality
Prove that for i ≥ 0, the (i + 2)nd Fibonacci number satisfies Fi+2 ≥ φi.
Follow @louis1992 on github to help finish this task.