文档介绍：数学基础
符说符号说明
取整函数
对数
阶乘
求和
估计和式的上界
递推方程求解
递推方程中涉及⎣x⎦和⎡x⎤的处理方法
1
符号说明
取整函数
⎣x⎦:小于等于x的最大整数
⎡x⎤:大于等于x 的最小整数
性质
x-1 < ⎣x⎦≤x ≤⎡x⎤< x+1
⎡ n ⎤⎢ n ⎥
⎢⎥+ ⎢⎥= n
⎢ 2 ⎥⎣ 2 ⎦
⎡⎡ n ⎤⎤⎢⎢ n ⎥⎥
⎢⎢⎥⎥⎢⎢⎥⎥
⎢⎢ a ⎥⎥⎡ n ⎤⎢⎣ a ⎦⎥⎢ n ⎥
= ⎢⎥, = ⎢⎥
⎢ b ⎥⎢ ab ⎥⎢ b ⎥⎣ ab ⎦
⎢⎥⎢⎥
⎢⎥⎣⎦ 2
对数函数
符号:
log n = log 2 n, (lg n = log 2 n)
log k n = (log n)k
log log n = log(log n)
性质:
a log b n = nlog b a
log k n = c log l n
3
阶乘
n 1
n!= 2πn( )n (1 + Θ( )) Stirling公式
e n
n! = o(nn)
2n=o(n!),
log n! = Θ(n log n)
4
求和
n x n +1 − 1
公式∑ x k =
k = 0 x − 1
n 1
∑= ln n + O (1)
k =1 k
n − 1 1 n − 1 1 1
例1 ∑= ∑( −)
k = 1 k ( k + 1 ) k = 1 k k + 1
nn−−111 1
= ∑−∑
kk==11k k + 1
n − 1 1 n 1 1
= ∑−∑= 1 −
k = 1 k k = 2 k n
5
例题
k k
例2 ∑ t 2 t − 1 = ∑ t(2 t − 2 t −1 )
t =1 t =1
k k k k −1
= ∑ t 2 t −∑ t 2 t −1 = ∑ t 2 t −∑(t + 1)2 t
t = 1 t =1 t =1 t = 0
k k −1 k −1
= ∑ t 2 t −∑ t 2 t −∑ 2 t = k 2 k −(2 k − 1)
t = 1 t = 0 t = 0
= (k − 1)2 k + 1
6
估计和式的上界
方法一:放大法
n
∑ak ≤ namax
k=1
a
k+1 ≤ r, 对于一切 k ≥ 0, r < 1为常数,则
ak
n ∞∞
k k a0
∑ak ≤∑a0r = a0 ∑ r =
k=0 k=0 k=0 1 − r
7
例题
例3 估计以下和式的上界
n k
∑ k
k = 1 3
k k + 1 a 1 k + 1 2
解 a = , a = , k+1 = ≤
k k k+1 k+1
3 3 ak 3 k 3
n k ∞ 1 2
≤( ) k
∑ k ∑
k = 1 3 k = 1 3 3
1 ∞ 2 1 1
≤( ) k = = 1
3 ∑ 3 3 2
k = 0 1 −
3 8
估计和式的界
方法二:利用积分
例4 调和数级数求和
n 1 n + 1 dx
≥= ln( n + 1 )
∑∫1
k = 1 k x
n 1 1 n 1 n dx
= + ≤ 1 + = ln n + 1
∑∑∫1
k = 1 k 1 k = 2 k x
9
积分作为上、下界
图1 调和数级数求和的积分近似 10