Recursive formula - alternating addition and suntraction

Question

So i got this formula that basically does this:

$$f(n) = n^2-(n-1)^2+(n-2)^2...$$ until it gets to $f(1)$ which is $1$.

The recursive form is: $$f(n)=n^2-f(n-1)$$

So is there a way to get to the closed form? As I do not know how to deal with the alternating + and -....thanks!

Answer 1

Note that the recursion is the equation $f(n)+f(n-1)=n^2, f(1)=1$. Note that if $f(n)$ is a polynomial of degree $p$, then $f(n)+f(n-1)$ is also a polynomial of degree $p$. Since it is equal to $n^2$, $f(n)$ is a polynomial of degree 2, i.e. a quadratic. Hence, if $f(n)=an^2+bn+c$, then

$$n^2=f(n)+f(n-1)=an^2+bn+c+a(n-1)^2+b(n-1)+c=$$$$2an^2+(2b-2a)n+(a-b+2c)$$

Equating coefficients, we have $2a=1,2b-2a=0,a-b+2c=0$. Hence, the solutions are $a=\frac12,b=\frac12,c=0$, so that $$f(n)=\frac12n^2+\frac12n=\frac{n(n+1)}{2}$$ This can be verified that it indeed satisfies both the recursion and the initial values, so the expression is correct.

Answer 2

Hint;

If you're looking for the sum representation, you can use $$\sum_{k}^n (-1)^k f(\cdot)$$ or $$\sum_{k}^n -(-1)^k f(\cdot)$$ accordingly to get alternating signs.

Answer 3

$$f(n) = n^2-(n-1)^2+(n-2)^2-...=\sum_{k=0}^n(-1)^k(n-k)^2$$

Answer 4

Rather simply, the answer is $$f(n)=\dfrac{n(n+1)}{2}$$ since it is equal to $n^2-\dfrac{(n-1)n}{2}.$ This is also $\displaystyle \sum_{k=1}^n k.$

Answer 5

Since $f(n)+f(n-1)=n^2$, we can try a quadratic polynomial, let $f(n)=an^2+bn+c$. Then $$an^2+bn+c+a(n^2-2n+1)+b(n-1)+c=2an^2+(2b-2a)n+2c+a=n^2,$$ $$2a=1\\2b-2a=0\\2c+a-b=0,$$ i.e. $a=b=1/2,c=0$, or $$f(n)=\frac{n^2+n}2.$$