Solving $T(n) = 3T(n-1) + 2$ I am trying to get better at solving recurrence relations, so I am making my own simple relations and try to solve them. I have made the following recurrence:

$$T(n) = 3T(n-1) + 2, \quad\quad T(1) = 1$$

My work at solving it:
$$\begin{align*}
T(n) &amp;= 3^2T(n-2) + 3*2 + 2 \\ 
     &amp;= 3^3 T(n-3) + 3^2*2+ 3*2 + 2 \\
     &amp;= 3^4 T(n-4) + 3^3*2 + 3^2*2 + 3*2 + 2 \\
    &amp;= \dots \\
  &amp;= 3^k T(n-k) + 3^{k-1}*2+3^{k-2}*2 +\dots+3*2+2 \\
 &amp;= 3^k + 3^{k-1}*2+3^{k-2}*2 +\dots+3*2+2 \\
&amp;= 3^k +[\sum_{i=1}^{k-1} 3^i*2 ] + 2
\end{align*}$$

where $k = n - 1$.

I guess the Big O would be exponential since the above would be less than $3^n$ which is $O(c^n)$?

I am stuck on how to finish this and find out what the time complexity is in Big O notation.
Let us add $1$ to both sides of your recurrence:
$$
T(n) + 1 = 3T(n-1) + 3 = 3(T(n-1) + 1).
$$
This shows that
$$
T(n) + 1 = 3^{n-1}(T(1) + 1),
$$
and so
$$
T(n) = 2 \cdot 3^{n-1} - 1.
$$