Define a recursive sequence for the following formula f(n) = n(n+1)

Question

Define a recursive sequence for the following formula f(n) = n(n+1).

Preferably one only defined by previous $a_n$ terms, i.e., no 'n' terms. If possible that is.

So for example the following produces: f(n) = n(n+1)

f(n+1) = (n+1)(n+2) $\implies$ f(n+1) - f(n) = $n^2 + 3n + 2 - n^2 - n$ = $2n + 2$ $\implies$ f(n+1) = 2n + 2 + f(n)

So that $a_n$ = $a_{n-1} + 2n + 2. $ with $a_1$ = 2.

However this has 'n' in the formula and I would hope to find a formula that only depends only on previous $a_i$ terms. I mean the Fibonacci numbers for example depends only on the previous 2 terms and not on 'n'.

Answer 1

The answer is

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

or, if you prefer,

$$a_n=3a_{n-1}-3a_{n-2}+a_{n-3}\qquad\text{with }a_0=0,a_1=2,a_2=6$$

This is based on $(x-1)^3=x^3-3x^2+3x-1$. If you're familiar with the Binet formula for Fibonacci numbers, the idea is to use a recursion relation that has $1$ as a repeated root. To get quadratic growth, it needs to be a cubic, so each value depends on the previous three terms.