Solve the recurrence relation T(n) = T(n-1) + 16lg(n)

Question

How would you go about solving the recurrence T(n) = T(n-1) + 16lg(n)? I don't think you can use the master method because it's T(n-1). I'm guessing you'd have to use iteration, but I'm not really sure how I would go about using that method. Any input would be great.

Answer 1

We have,

$$T(n)-T(n-1)=16 \lg n$$

We sum both sides from $n=1$ to $x$ to get:

$$\sum_{n=1}^{x} (T(n)-T(n-1))=\sum_{n=1}^{x} 16 \lg n$$

Notice that the left hand side is a telescoping sum.

$$T(x)-T(0)=\sum_{n=1}^{x} 16 \lg n$$

$$T(0)+\sum_{n=1}^{x} 16 \lg n=T(x)$$

Use properties of logarithms to show that this is,

$$16 \lg (x!)+T(0)=T(x)$$

Answer 2

Show by recurrence : $$T(n)=16\sum_{k=2}^n\ln(k)+T(1)$$ If you want an asymptotic approximation, you can use a comparison with an integral : $$\sum_{k=2}^n \ln(k)\approx \int_2^n \ln(t)\,dt \approx n\ln(n)$$