Proof request: If a function satisfies a polynomial recurrence then it is a polynomial

Question

Suppose we would like to find a formula for some interesting real-valued function on the positive integers $f(n):\mathbb{Z}^+\rightarrow\mathbb{R}$, and we have the inductive equation

$$\forall n\in\mathbb{Z}^+,\quad f(n+1)=f(n)+p(n)$$

for some polynomial $p(x):\mathbb{R}\rightarrow\mathbb{R}$. It should be intuitively obvious that $f(n)$ is also a polynomial, or at least that there exists a polynomial which is equal to $f(n)$ on the positive integers. Let $q(x):\mathbb{R}\rightarrow\mathbb{R}$ be such a polynomial:

$$ \forall n\in\mathbb{Z}^+,\quad f(n)=q(n) $$

Furthermore, the degree of $q(x)$ is one more than the degree of $p(x)$:

$$ \deg q(x) = \deg p(x) + 1$$

This allows the use of polynomial interpolation with the first $d+1$ points of $f(n)$ to calculate the coefficients of $q(x)$, and thus find a formula for $f(n)$. I would like a proof for the existence of the polynomial $q(x)$.

Proposition: If $f(n):\mathbb{Z}^+\rightarrow\mathbb{R}$ is a function such that there exists a polynomial $p(x):\mathbb{R}\rightarrow\mathbb{R}$ of degree $d$ such that $$\forall n\in\mathbb{Z}^+,\quad f(n+1)=f(n)+p(n)$$ then there exists a polynomial $q(x):\mathbb{R}\rightarrow\mathbb{R}$ of degree $d+1$ such that $f(n)=q(n)$ for all $n\in\mathbb{Z}^+$.

For example, let $f(n):\mathbb{Z}^+\rightarrow\mathbb{R}$ be the sum-of-squares function defined $$f(n) = \sum_{k=1}^{n} k^2$$

For all positive integers $n\in\mathbb{Z}^+$, the function $f(n)$ satisfies the equation

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

Let $p(x)$ be the polynomial of degree $2$ defined $p(x)=(x+1)^2$ for all $x\in\mathbb{R}$. From the proposition, there exists a polynomial $q(x)$ of degree $3$ such that $f(n)=q(n)$ for all $n\in\mathbb{Z}^+$. Thus, we can use polynomial interpolation with the points $f(1)=1$, $f(2)=5$, $f(3)=14$, and $f(4)=30$ to calculate the coefficients of $q(x)$. This yields: $$q(x) = \frac{1}{3}x^3 + \frac{1}{2}x^2 + \frac{1}{6}x$$ For $n\in\mathbb{Z}^+$, this matches the standard formula: $$f(n)=\frac{n(n+1)(2n+1)}{6}$$

This is a simple example, but this technique has helped me obtain formulas for complex recurrences simply by knowing what degree it will have.

Answer 1

Since $f(n+1)-f(n)=p(n)$, we have:

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

Thus, since $f(1)$ is a constant, we need to show $\sum_{i=1}^{n-1} p(n-1)$ is a polynomial of degree $k+1$, where $p$ is of degree $k$. Let $p(x)=\sum_{j=0}^k p_jx^j$, where $p_j$ are the coefficients of $p$. Thus, we have:

$$f(n)=f(1)+\sum_{i=1}^{n-1}\sum_{j=0}^kp_ji^j$$

Switch the order of summation:

$$f(n)=f(1)+\sum_{j=0}^k\sum_{i=1}^{n-1}p_ji^j$$

Now, by Faulhaber's Formula, $\sum_{i=1}^{n-1}p_ji^j$ is a polynomial of degree $j+1$ in terms of $n$. Thus, we are adding a polynomial of degree $0+1=1$ plus a polynomial of degree $1+1=2$ plus ... a polynomial of degree $k+1$. When we add polynomials of different degrees, the degree of the resulting polynomial is the maximum of the degree of the addends (i.e. a polynomial of degree $5$ plus a polynomial of degree $3$ is a polynomial of degree $5$). Thus, the resulting polynomial has degree $k+1$, which is exactly what we set out to prove.

Answer 2

If $f : \Bbb{Z} \to \Bbb{Z}$, let $\Delta f$ be defined by:

$$ \Delta f(n) = f(n) - f(n-1). $$

Then, $f$ is a polynomial function of degree $d$ iff $\Delta f$ is a polynomial function of degree $d - 1$. For your recurrence relation: $$ f(n+1) = f(n) + p(n) $$ where $p$ is a polynomial of degree $d$, $\Delta^d f$ will be a constant function implying that $f$ is a polynomial function of degree $d+1$.

(The above is very well-known and I am amazed that I can't find a link to an online reference for it. But searches for "method of differences", which is what I call the above theory, don't hit the spot.)

Answer 3

In my opinion, here is the easiest way to prove that, if $p(n)$ is a polynomial of degree $d$, then $q(n) =\sum_{k=0}^n p(k)$ is a polynomial of degree $d+1$.

Let $f_d(n) =\prod_{k=0}^{d} (n-k) $. This is a polynomial of degree $d+1$ in $n$.

Then

$\begin{array}\\ f_d(n+1)-f_d(n) &=\prod_{k=0}^{d} (n+1-k)-\prod_{k=0}^{d} (n-k)\\ &=\prod_{k=0}^{d} (n+1-k)-\prod_{k=1}^{d+1} (n-(k-1))\\ &=\prod_{k=0}^{d} (n+1-k)-\prod_{k=1}^{d+1} (n+1-k)\\ &=(n+1)\prod_{k=1}^{d} (n+1-k)-(n+1-(d+1))\prod_{k=1}^{d} (n+1-k)\\ &=(n+1)\prod_{k=1}^{d} (n+1-k)-(n-d)\prod_{k=1}^{d} (n+1-k)\\ &=(n+1-(n-d))\prod_{k=1}^{d} (n+1-k)\\ &=(d+1)\prod_{k=0}^{d-1} (n+1-(k+1))\\ &=(d+1)\prod_{k=0}^{d-1} (n-k)\\ &=(d+1)f_{d-1}(n)\\ \end{array} $

This shows that, for this particular type of polynomial, the difference of a polynomial of degree $d+1$ is a polynomial of degree $d$.

This, in turn, can be used to show by induction that the difference of a general polynomial of degree $d+1$ is a polynomial of degree $d$.

Summing this shows that the sum of a polynomial of degree $d$ is a polynomial of degree $d+1$.