1

This looks like an exponential recurrence due to the 3 behind $T$, but I'm not sure how to formally solve for $T(n)$ without $T$ on the righthand side.

Antonio Vargas
  • 24,993
David Faux
  • 3,425
  • 1
    do not sweat: [ http://www.wolframalpha.com/input/?i=t%281%29%3D1%2C+t%28n%29%3D3t%28n-1%29%2B2+n%2B2 ] – janmarqz Feb 02 '14 at 05:48

2 Answers2

4

Hint $$T(n)+n=3(T(n-1)+(n-1))+5$$

So we just solve $a_1=2$, $a_{n}=3a_{n-1}+5$.

Hint $$a_n+\frac{5}{2}=3(a_{n-1}+\frac{5}{2})$$

Then $b_1=\frac{9}{2}$ and $b_n=3b_{n-1}$.

gaoxinge
  • 4,434
2

Write $$ T(n)=A(n) 3^{n-1} $$ substituting $$ A(n+1) 3^n = 3 A(n) 3^{n-1}+ 2n + 2$$ Hence $$ A(n+1) = A(n) + \frac{2( n + 1)}{3^n}$$

Hence $$ A(n) = \sum_{k=1}^{n} \frac{k}{3^{k-1}} $$ Finally $$ T(n) = 3^{n-1} \sum_{k=1}^{n}\frac {k}{3^{k-1}}$$

There are some tricks to simplify the last summation.

user44197
  • 9,730