Solving a Recurrence with a Summation of Exponents as a Term

Question

This is totally a homework problem, but it's due in 27 minutes so I know I won't get anything in time for that. I don't want the answer, I just want to learn the technique. I've started a MS program but it's been over 30 years since my calculus classes.

I'm trying to solve the following recurrence:

$$ T(n) = 3T({n \over 2}) + 8n, \ T(1) = 1\ and \ n=2^k $$

I have gotten to this point, and cannot get any further despite my most frenetic Googling:

$$ T(n) = 3^k + 8 \sum_{j=0}^{k-1} 3^j {n \over 2^j} $$

The lectures for the class and all the other videos or pages I've found have either eliminated the initial exponential term completely and/or only have a simple exponential in the summation term (which is then solvable as a geometric summation).

It's now 16 minutes until deadline, but I still want to understand this so any pointers appreciated.

Randy

Answer 1

$$T(2^k) = 3T(2^{k-1}) + 8 \cdot2^k \tag{1}$$ $$T(2^{k-1}) = 3T(2^{k-2}) + 8 \cdot2^{k-1}\tag{2}$$ $$T(2^{k-2}) = 3T(2^{k-3}) + 8 \cdot2^{k-2}\tag{3}$$

$(3)$ in $(2) \implies$ $$T(2^{k-1}) = 3^2T(2^{k-3}) + 3 \cdot8 \cdot2^{k-2} + 8 \cdot2^{k-1} \tag{4}$$

$(4)$ in $(1) \implies$ $$T(2^k) = 3(3^2T(2^{k-3}) + 3 \cdot8 \cdot2^{k-2} + 8 \cdot2^{k-1}) + 8 \cdot2^k$$

Or, $$T(2^k) = 3^3T(2^{k-3}) + 3^2 \cdot8 \cdot2^{k-2} + 3 \cdot 8 \cdot2^{k-1} + 8 \cdot2^k$$

If you repeatedly substitute, ultimately you'll have

$$T(2^k) = 3^kT(2^{k-k}) + 8(3^{k-1}\cdot2^1 + 3^{k-2} \cdot 2^2 + \ldots + 3^{k-k} \cdot2^k) = 3^k + 8 \sum_{j=0}^{k-1}3^j 2^{k-j}$$

Or, $$T(2^k) = 3^k + 8 \sum_{j=0}^{k-1} 3^j \frac{n}{2^j}$$

Answer 2

As

$$ T\left(2^{\log_2 n}\right)=3T\left(2^{\log_2\left(\frac n2\right)}\right)+8n $$

calling now $\mathcal{T}\left(\cdot\right) = T\left(2^{(\cdot)}\right)$ and $z = \log_2 n$ we have the linear recurrence

$$ \mathcal{T}\left(z\right)=3\mathcal{T}\left(z-1\right)+2^{z+3} $$

and solving this recurrence we got

$$ \mathcal{T}\left(z\right)=3^{z-1}c_0+2^4(3^z-2^z) $$

and now going backwards with $z = \log_2 n$ we recover

$$ T\left(n\right) = 3^{\log_2 n-1}(3\cdot 2^4+c_0)-2^4n $$