How do I solve this recurrence equation using substitution?

Question

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

Using substitution, here are the first few steps: f(n-1) = f((n-1)-1) + 2((n-1)-1)

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

And then eventually I see that f(n+(-1)*2^j) = f(n+(-1)*2^(j+1)) + 2n + 2(-1)*2^(j+1), where j is an increasing integer >=1

What do I do now? It looks like 2(-1)*2^(j+1) will diverge to negative infinity...

The answer is f(n) = (n-1)n + 1 (using wolfram) but i have no idea what they did..

Answer 1

This is how it expands:

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

And you can see that we’ll get to $f(1) = 1$ eventually, and that will be when $n - a = 1$. So what this is actually saying is:

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

i.e.

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

So one plus twice the sum of $1$ to $n - 1$ inclusive, which is one plus twice the $n-1$th triangle number. The nth triangle number is $\dfrac{n^2 + n}2$, so the whole thing is:

$$1 + 2\left(\dfrac{(n-1)^2+(n-1)}{2}\right)$$ $$1 + (n - 1)^2 + n - 1$$ $$(n - 1)^2 + n$$ $$n^2 - 2n + 1 + n$$ $$n^2 + 1 - n$$ $$(n - 1)n + 1$$

… which is indeed what Wolfram got you!

Answer 2

Here’s the substitution reduction:

$$\begin{align*} f(n)&=f(n-1)+2(n-1)\\ &=f(n-2)+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\big(n-(k-1)\big)+\ldots+2(n-2)+2(n-1)\\ &\;\vdots\\ &=f(1)+2\big(n-(n-1)\big)+2\big(n-(n-2)\big)+\ldots+2(n-2)+2(n-1)\\ &=1+\sum_{k=1}^{n-1}2k\\ &=1+2\sum_{k=1}^{n-1}k\\ &\overset{*}=1+2\left(\frac{n(n-1)}2\right)\\ &=1+n(n-1)\\ &=n^2-n+1\;. \end{align*}$$

The formula for the sum of the first $n$ positive integers that I used at the starred step is a common special case of the more general formula for the sum of a finite arithmetic progression, one that’s worth knowing in its own right.