How to solve recurrence relation by iteration

Question

How exactly are those solved? Would appreciate an explenation as I cannot find a good one.

$$ \begin{cases} T(1)= 1 \\ f(n) = \log_2(n)\\ T(n) = a\, T(n-1) + f(n) \end{cases} $$

Answer 1

Well let's try $$T(n)=aT(n-1)+\log_2(n)$$ $$T(n-1)=aT(n-2)+\log_2(n-1)$$ So $$T(n)=a(aT(n-2)+\log_2(n-1))+\log_2(n)$$ $$=a^2T(n-2)+\log_2(n(n-1)^a)$$ $$=a^2(aT(n-3)+\log_2(n-2))+\log_2(n(n-1)^a)$$ $$=a^3T(n-3)+\log_2(n(n-1)^a(n-2)^{a^2})$$ So we can conjecture (and the proof by induction is left as an exercise) $$T(n)=a^kT(n-k)+\log_2(n(n-1)^a(n-2)^{a^2}\dots(n-(k-1))^{a^{k-1}})$$ So putting $k=n-1$, we get $$T(n)=a^{n-1}T(1)+\log_2(n(n-1)^a(n-2)^{a^2}\dots(2)^{a^{n-2}})$$ $$=a^{n-1}+\log_2(n(n-1)^a(n-2)^{a^2}\dots(2)^{a^{n-2}})$$ for all $n \ge 2$.

Note: trying $T(2)=a+1$ and then $T(3)=a(a+1)+\log_2(3)=a^2+a+\log_2(3)$ and we can substitute in the formula to find that it works: $$T(3)=a^2 + \log_2(3 \cdot 2^a)=a^2+a+\log_2(3)$$

Answer 2

Hint:

$$T(n)=f(n)+aT(n-1)=f(n) + a( f(n-1)+ a T(n-2))=$$ $$=f(n)+af(n-1)+a^2T(n-2)=$$ $$= f(n)+af(n-1)+a^2f(n-2)+ a^3T(n-3)=\cdots$$

Can you guess a formula? Once you have your guess, try to prove it is correct verifying it satisfies the relevant recursive relation.

Spoiler:

\begin{align} T(n)= f(n) +af(n-1) + \cdots + a^{n-2}f(2)+ a^{n-1}T(1) = a^{n-1} + \sum_{k=2}^{n} \log_2(k) a^{n-k} \end{align}