Why does the polynomial recurrence of $P(n)$ of degree $k$ requires a degree $k+1$ polynomial for its closed form?

Question

Suppose we have a recurrence defined in the following way:

$$a_n=a_{n-1}+n^2-3n$$ $$a_0 = 1$$

which produces the following sequence: $$1, -1, -3, -3, 1, ...$$

In order to find the polynomial closed form of this sequence given the recurrence, we start by saying that we need at least $n^3$. I would like to know why?

Answer 1

Considering the exemple you give, $(a_n-a_{n-1})$ is a quadratic expression; so $a_n$ will be a cubic function of $n$.

You could probably think about the similarity with derivatives : if $f'(x)$ is quadratic, then $f(x)$ is cubic.

Does this help you ?