如何求解递推关系式$f(n) = f(n/2) + n$？

嘿，我来一步步带你拆解这个递推关系式的解法，咱们用迭代展开法（也就是递推展开）来做，这是处理这类分治递推最直观的方法之一。

首先，我们先做个合理假设：假设$n$是2的幂次，也就是$n=2^i$（$i$为正整数），这样每次把$n$除以2都能得到整数，方便我们一步步展开递推式。另外默认边界条件为$f(1)=1$（这类递推问题通常会给出这个边界，这里我们就用这个标准边界来推导）。

第一步：逐步展开递推式 #

• 原递推式：$f(n) = f(n/2) + n$
• 先把$f(n/2)$用递推式本身展开：$f(n/2) = f(n/4) + n/2$，代入原式后得到：
  $$f(n) = f(n/4) + n/2 + n$$
• 再继续展开$f(n/4)$：$f(n/4) = f(n/8) + n/4$，代入后又得到：
  $$f(n) = f(n/8) + n/4 + n/2 + n$$
• 按照这个规律一直展开下去，直到递推到边界$f(1)$。

第二步：归纳展开后的通项 #

当我们展开$i$次后（因为$n=2^{i$，所以除以$2}i$就得到1），递推式会变成：
$$\begin{split}
f(2^i) &= f(2^i/2i) + \frac{2^i}{2{i-1}} + \frac{2^i}{2{i-2}} + \dots + 2^i\
&= f(1) + 2^1 + 2^2 + \dots + 2^i
\end{split}$$

第三步：计算等比数列的和 #

这里的$2^1 + 2^2 + \dots + 2^{i$是一个首项为2、公比为2的等比数列，根据等比数列求和公式，它的和是$2}{i+1} - 2$。

代入边界条件$f(1)=1$后：
$$\begin{split}
f(2^i) &= 1 + (2^{i+1} - 2)\
&= 2^{i+1} - 1
\end{split}$$

因为我们一开始设了$n=2^{i$，所以$2}{i+1}=2 \times 2^i=2n$，替换后就得到最终的结果：
$$f(n) = 2n - 1$$

另外注意：你提供的内容里后面还有一段关于$f(n)=\log_2 n +1$的推导，那其实是递推式$f(n)=f(n/2)+1$的解，和咱们当前的递推式$f(n)=f(n/2)+n$无关，应该是粘贴时不小心混进来的，别搞混啦～

备注：内容来源于stack exchange，提问作者Aizaz Ullah Khan Niazi