Problemas para entender o teorema mestre, nas Notas de Jeffrey Erickson

Estou olhando as notas de Jeffrey Erickson sobre o teorema dos mestres (página 10).

A parte (b) do teorema afirma que se , e então T (n) é . Mas eu recebo um resultado diferente.$T(n) = aT(\frac{n}{b})+f(n)$$af(\frac{n}{b}) = kf(n)$$k>1$$\Theta(n^{\log_b(a)})$

Usando árvores de recursão, temos

$$T(n) = \sum_{i=0}^{\log_b(n)} a^i f\left(\frac{n}{b^i}\right) = \sum_{k=0}^{\log_b(n)} k^i f(n)\,.$$

Se então é conforme desejado. Se então é conforme desejado. Mas se então esta é uma série geométrica ascendente, então o último termo domina. Então temos que está errado; a resposta certa é . Onde meu raciocínio sai dos trilhos e qual é a solução correta?$k<1$$\sim f(n)$$k=1$$\sim \log_b(n)f(n)$$k>1$

$$\sim k^{\log_b(n)}f(n) = n^{\log_b(k)}f(n)\,,$$ $\Theta(n^{\log_b(a)})$

Qualquer ajuda é apreciada.

Edição: Eu acho que minha resposta está realmente certa e é equivalente à resposta mais simples de Erickson. Observe que Portanto, .$k^nf(n) = k^{n-1}af(\frac{n}{b}) ... = ka^{n-1}f(\frac{n}{b^k-1}) = a^nf(\frac{n}{b^k}).$$k^{\log_b(n)}f(n) = a^{\log_b(n)}f(1) \sim n^{\log_b(a)}$

Você pode simplificar ainda mais .$n^{\log_b(k)}f(n)$

Temos . Se , podemos aplicar essa identidade vezes para obter .$\frac{a}{k}f(\frac{n}{b}) = f(n)$$c = \log_b(n)$$c$$\left(\frac{a}{k}\right)^c f(1)$

Então$n^{\log_b(k)}f(n) = n^{\log_b(k)}\left(\frac{a}{k}\right)^c f(1) = k^{\log_b(n)}\left(\frac{a}{k}\right)^{\log_b(n)} f(1) = a^{\log_b(n)}f(1) = \Theta(n^{\log_b(a)})$