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?

score 0 · Answer 1 · answered Oct 09 '15 at 07:37

0

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 ?

answered Oct 09 '15 at 07:37

Claude Leibovici

260,315

I do not see any intuition behind what you've said. I don't see how $a_n - a_{n-1}$ being quadratic has anything to do with $a_n$ being cubic. Is there something you've skipped or am I missing something really simple? – ChaoSXDemon Oct 09 '15 at 07:55

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

1 Answers1