递归关系式的大O符号归纳法证明：如何完成n+1步推导？

嘿，我来帮你补全这个归纳证明的步骤，先理清楚整个逻辑：

首先我们要处理的递归式是：
$$T(1) = 4 $$
$$T(n) = 2T(\frac n2) +5n,\qquad n\geq 2 $$
目标是证明它属于$O(n·log₂n)$，你已经选好了常数$C=9$、$k=2$，基例也验证通过了，接下来我们把归纳步骤补全，顺便说下你提到的$n+1$步的误区~

已完成的验证环节 #

• 基例（$n=2$）：
  代入递归式计算得$T(2)=2·T(1)+5·2=8+10=18$，而$9·2·log₂(2)=9×2×1=18$，刚好满足$18≤18$，完全符合大O定义的基例要求。
• 归纳假设：

  这里需要稍微修正下你的假设表述——因为这个递归式是分治结构，输入规模是按$n/2$缩小的，更准确的归纳假设应该是：对于所有满足$2≤m<n$的正整数$m$，$T(m) ≤9·m·log₂(m)$成立（强归纳法）；如果只考虑$n$是2的幂的情况，也可以假设当$n=2^k$时，$T(n/2) ≤9·(n/2)·log₂(n/2)$成立。

补全归纳推导步骤 #

我们需要证明：对于任意$n≥2$，$T(n) ≤9·n·log₂(n)$成立。

根据递归式的定义，$T(n)=2T(n/2)+5n$，把归纳假设的$T(n/2) ≤9·(n/2)·log₂(n/2)$代入进去：
$$
\begin{align*}
T(n) &≤2×\left[9·\frac{n}{2}·log₂\left(\frac{n}{2}\right)\right] +5n \
&=9n·log₂\left(\frac{n}{2}\right)+5n \
&=9n·(log₂n - log₂2)+5n \quad \text{（利用对数的除法性质：$log₂(a/b)=log₂a - log₂b$）} \
&=9n·log₂n -9n +5n \
&=9n·log₂n -4n \
\end{align*}
$$
因为$n≥2$，所以$-4n$是负数，显然有：
$$T(n) ≤9n·log₂n -4n ≤9n·log₂n$$
这就完美满足了我们要证明的不等式，归纳步骤直接成立。

关于你提到的$n+1$步的说明 #

这里要注意：这个递归式不是线性递推（比如斐波那契那种每次加1的规模），而是分治递推，规模是按除以2缩小的，所以我们不需要去证明$n+1$的情况，而是基于更小的$n/2$的情况来推导更大的$n$。

如果要覆盖所有整数$n$（不只是2的幂），可以用强归纳法处理奇数的情况：假设$n$是奇数，那么$\lfloor n/2 \rfloor <n$，代入归纳假设：
$$
\begin{align*}
T(n) &=2T(\lfloor n/2 \rfloor)+5n \
&≤2×\left[9·\lfloor n/2 \rfloor·log₂(\lfloor n/2 \rfloor)\right] +5n \
&≤2×\left[9·\frac{n}{2}·log₂\left(\frac{n}{2}\right)\right] +5n \quad \text{（因为$\lfloor n/2 \rfloor ≤n/2$，且$log₂x$是递增函数）} \
&=9n log₂\left(\frac{n}{2}\right)+5n \
&=9n(log₂n -1)+5n \
&=9n log₂n -4n ≤9n log₂n
\end{align*}
$$
同样满足不等式，所以不管$n$是奇数还是偶数，归纳都成立。

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