# Solve the following recurrence

I'm trying to solve this the recurrence : $$T(n)=\begin{cases} 1, & \text{ if } n = 1 \\ T(n-1) +n(n-1), & \text{ if } n \geq 2 \end{cases}$$

• $1 + \dfrac{(n-1)n(n+1)}3$, if you want a closed formula. – John L. Apr 24 at 16:21
• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Apr 24 at 21:58

## 1 Answer

Since $$T(n)=T(n-1)$$, using induction we can prove that $$T(n)= 1 + \sum_{k=1}^n k(k-1) \le 2\sum_{k=1}^n k(k-1)$$

Now, calculating $$\sum_{k=1}^n k(k-1)$$ gives us:

$$\sum_{k=1}^n k(k-1)=\sum_{k=1}^n (k^2 - k) = \sum_{k=1}^n k^2 - \sum_{k=1}^n k$$

Using this formula, we know that $$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$, and its not hard to show that $$\sum_{k=1}^n k = \frac{n (n+1)}{2}$$

Therefore, $$T(n) \le 2\left(\frac{n(n+1)(2n+1)}{6} - \frac{n (n+1)}{2}\right) = O(n^3)$$

• A lower bound can be given using the same proof, replace the $\le$ with $\ge$ and replace the multiplication by $2$ with multiplication by $\frac{1}{2}$ – nir shahar Apr 24 at 14:07
• I don't understand the second step. Can you explain that line? – Phȕc Luog Apr 24 at 14:25
• Can you be more specific about what you didn't understand? What equation in the line don't you understand? – nir shahar Apr 24 at 14:26
• The line that you using induction to prove $$T(n)=1+∑nk=1k(k−1)≤2∑nk=1k(k−1)$$ – Phȕc Luog Apr 24 at 14:38
• $T(n)=T(n-1)+n(n-1)=T(n-2)+(n-1)(n-2)+n(n-1)=T(n-3)+(n-2)(n-3)+(n-1)(n-2)+n(n-1)=...=T(1) + \sum_{k=1}^n k(k-1) = 1 + \sum_{k=1}^n k(k-1)$ – nir shahar Apr 24 at 14:39