How to find an explicit formula for a recurrence using substitution 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?
 A: 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.
A: 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}$$
