How to solve recurrence relation: f(n) = f(n-1) + 2(n-1) when f(1) = 1?

Question

I am just learning about recurrence relations, and this is an absolute beginner's question. I understand what's going on in the formula, but I have no clue how to write it's solution?

This probably takes no time at all to answer, but thought some helpful people on the Internet can save me the embarrassment of asking someone in person haha.

f(1) = 1
f(n) = f(n-1) + 2(n-1)

from this equation, I extracted the values:

f(2) = 3
f(3) = 7
f(4) = 13
... etc

meaning the differences between each are increments of 2, starting from 2. How would I write the closed equation for this?

Thanks!

Added bonus (I really only need the first one): In a more computer science approach to this question, what would the time complexity for this question be?

Answer 1

Hint: $$ \sum_{k=1}^nk=\frac{n^2+n}{2} $$

Answer 2

Notice that $f(k) - f(k-1) = 2(k-1).$ Now sum this relation $1\le k \le n$.

Answer 3

One approach is to ‘unwrap’ the recurrence:

$$\begin{align*} f(n)&=f(n-1)+2(n-1)\\ &=\Big(f(n-2)+2(n-2)\Big)+2(n-1)\\ &=f(n-2)+2(n-2)+2(n-1)\\ &=\Big(f(n-3)+2(n-3)\Big)+2(n-2)+2(n-1)\\ &=f(n-3)+2(n-3)+2(n-2)+2(n-1)\\ &\;\vdots\\ &=f(n-k)+2(n-k)+2(n-k+1)+\ldots+2(n-1)\\ &\;\vdots\\ &=f\big(n-(n-1)\big)+2\big(n-(n-1)\big)+\ldots+2(n-1)\\ &=f(1)+2(1)+2(2)+\ldots+2(n-1)\\ &=1+2\sum_{k=1}^{n-1}k\;. \end{align*}$$

You probably know a formula for the sum of the first so many positive integers; substitute that into the last line, and you’ll have your closed form. Note that this isn’t really a proof that the closed form is correct: the $k$ line in the middle represents an inference that we’ve spotted the right pattern. A complete solution would take the closed form that you get and prove by induction on $n$ that it actually does satisfy the recurrence.