以下是我对主定理的部分证明，但是写完这部分后感觉不太确定，请大佬指点一下。

证明：

在忽略常数 $c$ 的情况下，没有递归前，需要 $n^d$ 做运算。

我们考虑第一次递归：

共有 $a$ 个子问题，每个子问题运算需要花费 $(\frac{n}{b})^d$ 的时间。

那么一共就要花费 $a \times \frac{n^d}{b^d}=\frac{a}{b^d} \times n^d$ 的时间来运算第一次递归。

那么类似的，考虑第二次递归：

共有 $a^2$ 个子问题，每个子问题需花费 $(\frac{n}{b^2})^d$ 的时间来运算。

那么总共就要花费 $a^2 \times (\frac{n}{b^2})^d=(\frac{a}{b^d})^2 \times n^d$ 的时间。

以此类推，到第 $k$ 次递归时：

共有 $a^k$ 个子问题，每个子问题需花费 $(\frac{n}{b^k})^d$ 的时间来运算。

那么总共就要花费 $(\frac{a}{b^d})^k \times n^d$ 的时间。

这里如果不懂的话可以自己画个递归树理解。

总共有 $\log_bn$ 次递归，将所有的递归所花费的时间加起来就是总时间。

即 $T(n)=\Sigma^{\log_bn}_{i=0} ((\frac{a}{b^d})^i \times n^d)$

可以将 $T(n)$ 进一步处理：

$T(n)=\Sigma^{\log_bn}_{i=0} ((\frac{a}{b^d})^i \times n^d)=n^d \times(\Sigma^{\log_bn}_{i=0}(\frac{a}{b^d})^i)$

显然可以发现，这是个等比数列求和。

令 $(\frac{a}{b^d})=q$

则有：

$T(n)=n^d \times \Sigma^{\log_bn}_{i=0} q^i=n^d \times \frac{(1-q^{k+1})}{1-q}$

考虑特殊情况 $q=1$ 的时候。

此时就相当于 $a=b^d$ (将 $q$ 代回)。

此时数列元素全部为 $1$。

那么显然 $T(n) = n^d \times (\log_bn+1)$

目前写到这一步，发现 $T(n)$ 里面有个(log+1)，请问我到目前为止的证明都是正确的吗？