f(x)>f(x−1)+f(x−2),x<3 时 f(x)=x。
f(3)>f(2)+f(1)=2+1=3。f(4)>f(3)+f(2)>3+2=5。f(5)>f(4)+f(3)>5+3=8。
递推 f(n)>f(n−1)+f(n−2),类似斐波那契增长(但严格大于)。
设 g(n)=f(n) 的下界为斐波那契型数列 Fn:F1=1,F2=2,Fn=Fn−1+Fn−2。
F:1,2,3,5,8,13,21,34,55,89,144,…
f(10)>F10=89。检查 A: f(10)>100?F10=89<100,但 f 增长可能快于 F。
更紧的下界:f(n)>f(n−1)+f(n−2)>Fn−1+Fn−2=Fn。F10=89,f(10)>89。但 89<100,A 不一定成立。
实际上 f(n) 的精确下界为 Fn,F10=89<100,F20=10946>1000。
f(20)>F20=10946>10000?F20=10946>10000,故 D (f(20)<10000) 错误。
B: f(20)>1000?F20=10946>1000。✓
C: f(10)<1000?f(10)>89,但 f(10)<1000 是否成立?f(10) 可任意大(增长快于斐波那契),但题目问哪些一定成立。
f(10)>89,但 f(10) 可远大于 1000(若每步增长远超 Fn),故 C 不一定成立。
A: f(10)>100?F10=89<100。但 f 严格大于 F,每步多出可累积。f(3)>3,f(4)>f(3)+2>5,f(5)>f(4)+f(3)>8... 严格递推下界恰为 Fn,F10=89<100。A 不一定成立。
但更仔细:f(3)≥3+ϵ(ϵ>0),ϵ 逐级放大。f(10)≥F10+c⋅ϵ(c 为系数),但 ϵ 可任意小,故 f(10)>89 但不一定 >100。
B: f(20)>F20=10946>1000。✓ D: f(20)>10946>10000,D 错误。
答案
正确结论为 B。