顺序统计量递推关系归纳证明与阈值设定问题咨询

问题1：归纳法证明 $T(n) \le 20cn$ #

我们通过常规数学归纳法即可完成证明，步骤如下：

• 归纳基础：当 $n \le 49$ 时，根据题目给出的递推定义，直接有 $T(n) \le cn$，显然 $cn \le 20cn$（$c$ 为正的常数系数），基础情况成立。
• 归纳假设：假设对于所有小于 $n$ 的正整数 $k$（此时 $n \ge 50$），都满足 $T(k) \le 20ck$。
• 归纳推导：对于 $n \ge 50$ 的情况代入递推式：
  $$
  \begin{align*}
  T(n) &\le T\left(\frac{n}{5}\right) + T\left(\frac{3n}{4}\right) + cn \
  &\le 20c \cdot \frac{n}{5} + 20c \cdot \frac{3n}{4} + cn \
  &= 4cn + 15cn + cn \
  &= 20cn
  \end{align*}
  $$
  即便考虑实际算法中子问题规模需要取整（比如 $\lceil n/5 \rceil$、$\lceil 3n/4 \rceil$），由于 $n \ge 50$ 时取整带来的误差极小，且规模小于等于49的子问题本身满足 $T(k) \le ck \le 20ck$，远小于归纳假设的上界，推导结果依然成立。

问题2：阈值选择49/50的原因 #

这个阈值是配合递推式和证明过程选择的最优边界，核心原因有两个：

1. 保证递推收敛：当 $n \ge 50$ 时，两个子问题的规模之和为 $\frac{n}{5} + \frac{3n}{4} = \frac{19n}{20}$，严格小于原问题规模 $n$，确保递归过程的规模会持续缩小，最终落到基础情况区间，不会出现无限递归。
2. 适配归纳证明的常数：本次证明用到的上界系数是20，刚好满足 $20 \times (\frac{1}{5} + \frac{3}{4}) = 19$，剩余的系数1刚好抵消递推式里的 $cn$ 项，整个推导过程不需要额外调整常数。同时所有 $n \le 49$ 的情况都满足 $T(n) \le cn \le 20cn$，可以直接作为归纳基础，不需要额外拆分边界情况。
   这个阈值并不是唯一的，只要满足上述两个条件的数值都可以使用，选择49/50是最简化证明过程的方案。

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