3.2-1 证明：若f(n)和g(n)是单调递增的函数，则f(n)+g(n)和f(g(n))也是单调递增的；另外，若f(n)和g(n)是非负的，那么f(n)*g(n)是单调递增的。
证：若n1>n2,则有f(n1)+g(n1) - f(n2) - g(n2) = (f(n1) - f(n2)) + (g(n1) - g(n2))，由题意可知，f(n) 和 g(n)是单调递增的，可知f(n)+g(n)也是单调递增的。
若n1>n2,则有g(n1) >= g(n2)，显然有f(g(n1)) >= f(g(n2)),可知f(g(n))是单调递增的。
若n1>n2, f(n1) >0, 则f(n1)*g(n1) - f(n2)*g(n2) = f(n1)(g(n1) - g(n2) * f(n2)/f(n1))，其中0 <= f(n2)/f(n1) <= 1。则g(n2)*f(n2)/f(n2) <= g(n2) <= g(n1)，显然f(g(n))也是单调递增的。
3.2-2 不证了
3.2-3 证明等式n!=o(n^n), n!=w(2^n), lg(n!)=θ(nlgn)。并证明n!=w(2^n)和n!=o(n^n)。
证：根据斯特林公式，n!=((2πn)^(1/2))*((n/e)^n)*(1+θ(1/n)),存在任意的正常数c>0,n0>0，当n0->正无穷， ((2πn)^(1/2))*((1/e)^n)*(1+θ(1/n)) ->0，显然有 0 <= ((2πn)^(1/2))*((n/e)^n)*(1+θ(1/n)) <= c (n^n)，得证 。
假设要存在任意的正常数c>0,n0>0,当n>n0,有 0 <= c2^n < n!成立，则 n!/(2^n) =((2πn)^(1/2))*((n/(2e))^n)*(1+θ(1/n)),显然n0->无穷，n!/(2^n)->无穷，得证。
同理，假设存在正常数c1>0,c2>0,n0>0,当n>n0,有c1nlgn< lg(n!) < c2nlgn。即当n0->正无穷，则n!=lg(((2πn)^(1/2))*((n/e)^n))*(1+θ(1/n)))/(nlgn) ->1，则可知必然存在c1、c2，有c1 <= 1 <=c2,得证。
3.2-4 函数ceiling(lgn)!是否多项式有界？函数floor(lglgn)!呢？
3.2-5 哪一个在渐进上更大些：lg(lg*n)还是lg*(lgn)
答：举例说明，n=16, lg(lg*n) = lg3, lg*(lgn) = 2; n = 65536,lg(lg*n) = 2, lg*(lgn) = 3; 由此可见，后者渐进更大。
3.2-6 用归纳法证明：第i个菲波那契数满足等式：
Fi = (φ^i -φ'^i)/(5^(1/2))，前者是黄金分割率，后者是共轭数。
证明：当n=1,显然F1 = 1,满足条件。
当n=k，k+1,若假设也成立，即
Fk = (φ^k- φ'^k)/(5^(1/2))，Fk+1 = (φ^（k+1）- φ'^（k+1）)/(5^(1/2))。
则n=k+2时，按照公式，有Fk+2 = (φ^(k+2)- φ'^(k+2))/(5^(1/2))，按照菲波那契函数
Fk+2 = Fk + F(k+1) =(φ^(k+2)- φ'^(k+2))/(5^(1/2))，因此成立。得证
3.2-7 证明：对于i>=0,第（i+2）个菲波那契数满足Fi+2 >= φ^i。
证：Fk+2 - φ^k= (φ^(k+2)- φ'^(k+2))/(5^(1/2)) -φ^k = Fk * (3-5^(1/2)) / 2 > 0 ，显然已证明。