# 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 &\text{if }n=1,\\ T(n−1)+3n &\text{if }n>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?

• A tree node that only has one child will still constitute a tree. Consider the fact that a linked list is also a tree. So instead of having 2 subproblems here, you only have 1, of size $n-1$. – ryan Apr 15 '19 at 16:12

Expanding the recursion, we get \begin{align*} T(n) &= 3n + T(n-1) \\ &= 3n + 3(n-1) + T(n-2) \\ &= 3n + 3(n-1) + 3(n-2) + T(n-3) \\ &= \cdots \\ &= 3n + 3(n-1) + 3(n-2) + \cdots + 3(2) + T(1) \\ &= 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.