How to find an explicit formula for a recurrence using substitution

Question

I have a recurrence as follows: \begin{equation} T(n) = \begin{cases}a, & \text{for $n=1$}\\ T(\dfrac{n}{2})+b,&\text{for $n\geq2$} \end{cases} \end{equation} $a$ and $b$ are some undefined constant.

I'm asked to find an explicit formula using substitution, showing my work for $k$ iterations. I understand, conceptually, how to substitute: \begin{align*} T(n) &= T(n/2)+b\\ T(n/2) &= T(n/4) + 2b\\ T(n/4) &= T(n/8) + 3b\\ T(n/8) &= T(n/16) + 4b \end{align*}

WolframAlpha tells me that this recurrence resolves to $T(n) = a + \dfrac{b \log(n)}{\log(2)}$, but I have no idea how it arrived there, or if that is even correct.

What is the correct way to perform this substitution to arrive at an explicit formula?

Answer 1

First, one can notice that this recurrence is defined only for numbers $n$ which are powers of 2.

To solve the recurrence, you can try to unravel it.

Namely, $$T(n) = b+T\left(\frac{n}{2}\right) = b+b+T\left(\frac{n}{4}\right)= b+b+b+T\left(\frac{n}{8}\right) = 3b+T\left(\frac{n}{2^3}\right)$$

We can see that the coefficient next to $b$ increases by one in every step and that the argument of $T$ gets divided by two every time. So, we can infer that the general formula would be: $$T(n) = k\cdot b + T\left(\frac{n}{2^k}\right)$$ for some $k\in\mathbb N$.

But, we are aiming to get $n=2^k$, in order for the chain to terminate. This gives us that $k=\log_2 n$.

Now we have $$T(n) = b\log_2 n + T(1) = b\log_2 n+a$$

You can use mathematical induction to prove that this is indeed the general formula for $T(n)$.

Also, this formula is equivalent to the formula WolframAlpha gave.

Answer 2

It might be useful to rewrite the recursion as follows:

• $\boxed{n=2^k} \Rightarrow \boxed{t_k = T(2^k)}$
• $\Rightarrow \boxed{t_{k+1} = t_k + b, t_0 = a}$ for $k \in \mathbb{N}$
• Telescoping gives $\boxed{t_k} = t_0 + \sum_{i=0}^{k-1} (t_{i+1} - t_i) \boxed{= a + kb}$
• Having in mind that $n=2^k \Leftrightarrow k = \log_2 n = \frac{\ln n}{\ln 2}$ you get: $$\boxed{T(n) = a+ b\cdot \log_2 n} \mbox{ for } n= 2^k, k \in \mathbb{N}$$