How is the Solution to the Given Recurrence Relation Derived?

[mathmari]

Hey!

I need some explanations at the proof of the following theorem.

Theorem:

Let $a$, $b$ and $c$ be nonnegative constants.

The solution to the recurrence $$T(n)=\left\{\begin{matrix}
b & ,\text{ for } n=1\\
aT(n/c)+bn & ,\text{ for } n>1
\end{matrix}\right.$$
for $n$ a power of $c$ is $$T(n)=\left\{\begin{matrix}
O(n) & ,\text{ if } a<c\\
O(n \log n) & ,\text{ if } a=c\\
O(n^{\log_c a}) & ,\text{ if } a>c
\end{matrix}\right.$$

Proof:

If $n$ is a power of $c$, then $$T(n)=bn \sum_{i=0}^{\log_c n} r^i, \text{ where } r=a/c$$

If $a<c$, then $\displaystyle{\sum_{i=0}^{\infty}r^i}$ converges, so $T(n)$ is $O(n)$.

If $a=c$, then each term in the sum is unity, and there are $O(\log n)$ terms. Thus $T(n)$ is $O(n \log n)$.

Finally, if $a>c$ then $\displaystyle{bn\sum_{i=0}^{\log_c n} r^i=bn\frac{r^{1+\log_c n}-1}{r-1}}$, which is $O(a^{\log_c n})$ or equivalently $O(n^{\log_c a})$.
My questions are the following:

1. Why is $T(n)$ equal to $bn \sum_{i=0}^{\log_c n} r^i$, where $r=a/c$ if $n$ is a power of $c$ ??

2. If $a<c$: why does $\displaystyle{\sum_{i=0}^{\infty}r^i}$ converge??

3. If $a=c$: why is each term of the sum unity??

4. If $a>c$: why does $\displaystyle{bn\sum_{i=0}^{\log_c n} r^i=bn\frac{r^{1+\log_c n}-1}{r-1}}$ only in this case??

(Wondering)

 

[Valkarie]

1. The recurrence relation states that $T(n)$ is equal to $aT(n/c)+bn$ for $n>1$. This can be rewritten as $T(n)=aT(n/c) + bn$, which can then be expanded as $T(n)=aT(n/c)+ aT(n/c^2)+...+aT(n/c^{\log_cn})+bn$. Since $T(1) = b$, the result follows. 2. When $a < c$, the sum $\displaystyle{\sum_{i=0}^{\infty}r^i}$ converges since $|r| < 1$.3. When $a = c$, the sum $\displaystyle{\sum_{i=0}^{\log_c n}r^i}$ has each term equal to unity since $r = 1$.4. When $a > c$, the sum $\displaystyle{bn\sum_{i=0}^{\log_c n} r^i=bn\frac{r^{1+\log_c n}-1}{r-1}}$ because it can be rearranged to be in the form of a geometric series with common ratio $r$ and $n$ terms.