Guidance on solving a recurrence relation

Question

I am trying to solve the following recurrence:

$T(1) = 2$, and for all $n\ge2$, $T(n) = T(n-1) + n - 1$

By using repeated substitutions, I was able to discern the following formula:

$$T(n)=T(n-i) + ni + \sum_{j=1}^ij$$

I am trying to prove, by induction, that this is a good guess for a formula. However, I am getting hung up trying to prove it.

So far I have the following:

$$T(n)=T(n-i) + ni + \sum_{j=1}^ij$$ $$=T(n-(i-1)) + n(i-1) + \sum_{j=1}^{i-1}j$$ $$=T(n-i)+n-(i+1)+n(i-1) + \sum_{j=1}^{i-1}j$$

After this step I am totally lost, and I am not even sure if what I have done so far is even correct. Most of the induction proofs I have done have just been summations, so I am not very skilled at proving recurrences yet. Any help in pointing me in the right direction or showing me where I am mistaken is greatly appreciated.

Edit I think my main issue (at least from what I can tell) is not knowing what to use for the inductive step. I am trying to prove $T(n)=T(n-i) + ni + \sum_{j=1}^ij$ by induction, which holds when $i=1$. After this, I am confused about how to approach the inductive step. Everything I try, I cannot simplify or I am just making a mistake somewhere. Help is appreciated.

Answer 1

The first time you apply the recurrence, you are adding $n-1$. Then you recurse again and add $n-2$. This goes all the way down until finally you add $1$ for $T(2)$ and then add 2 for $T(1)$ for the initial condition. So you want to compute $T(n) = 2 + \sum_{j=1}^{n-1} j$. This is a standard summation with a simple formula, you can just look up "sum of consecutive integers".

Answer 2

You can apply the recurrence until you hit the bottom at argument 1: $$ T(n) = T(1) + \sum_{k=n-1}^1 k = 2 + \frac{(n-1)n}{2} =: A(n) $$ For a proof we first check $n=1$, thus if the initial condition is fulfilled: $$ A(1) = 2 + \frac{0\times 1}{2} = 2 = T(1) $$ If $A(n) = T(n)$ for $n$, then $$ A(n+1) = 2 + \frac{(n+1-1)(n+1)}{2} = 2 + \frac{n(n-1)}{2} + \frac{2n}{2} = T(n) + n = T(n+1) $$ By the principle of induction we deduce $A(n) = T(n)$ for all $n\in \mathbb{N}$.