How to find closed form solution of linear recursion using recursive tree method I want to be able to find closed form runtime solution for recursive insertion sort which looks something like this

$$T(n)=\begin{cases}
    1         &amp;\text{if }n=1,\\
    T(n−1)+3n &amp;\text{if }n&gt;1.
\end{cases}$$

However, I am confused about how to plot a tree. I know how to find runtime using tree if problem is divided into half. But here problem is just reduced by one. How does it work?
Expanding the recursion, we get
$$
\begin{align*}
T(n) &amp;= 3n + T(n-1) \\ &amp;= 3n + 3(n-1) + T(n-2) \\ &amp;= 3n + 3(n-1) + 3(n-2) + T(n-3) \\ &amp;= \cdots \\ &amp;= 3n + 3(n-1) + 3(n-2) + \cdots + 3(2) + T(1) \\ &amp;=
3n + 3(n-1) + 3(n-2) + \cdots + 3(2) + 1.
\end{align*}
$$
Therefore
$$
T(n) = 1 + \sum_{m=2}^n 3m.
$$
You take it from here.