求三项式系数上界的正确计算方法与推导思路

求解方案 #

核心思路：先对通项做基础放缩，再计算求和上界 #

你不需要对求和项做复杂拆分，通过基础不等式对通项$(i!)^{1/i}$放缩就能快速推导：

1. 对任意正整数$i$，有$i! \leq i^i$，两边开$i$次方可得：
   $(i!)^{1/i} \leq i$
2. 将该放缩代入原式$\sum_{k=1}^n \sum_{i=1}^k (i!)^{1/i}$，可以得到上界：
   $\sum_{k=1}^n \sum_{i=1}^k i$
3. 先计算内层求和：
   $\sum_{i=1}^k i = \frac{k(k+1)}{2} = O(k^2)$
4. 再计算外层求和：
   $\sum_{k=1}^n O(k^2) = O(n^3)$

更紧的上界推导（可选） #

如果需要更精确的渐近上界，可以用斯特林公式做近似：
由斯特林公式$\ln i! = i\ln i - i + O(\ln i)$，两边除以$i$后取指数可得：
$(i!)^{1/i} = \frac{i}{e} \cdot (1+o(1))$
代入求和后最终可以得到紧上界为$\frac{n^3}{6e}(1+o(1))$，说明$O(n^3)$是无法再降低量级的最优上界。

你之前的推导复杂度高，是因为选择了拆分求和项的方向，优先对通项做量级放缩才是这类求和上界问题的最优解法。

内容的提问来源于stack exchange，提问作者sban346