Prove certain recursive functions are polynomials

Question

Problem: Derive a formula for $\sum_{k=1}^n k^2$.

Attempt: Let $f(n)$ be such a formula. Then we have the recursive formula $$\forall n\in\mathbb{N},\quad f(n+1)=f(n)+(n+1)^2$$ and the initial condition $f(1)=1$. We wish to prove that $f(n)$ is a polynomial of degree $3$, for which the coefficients can be found through polynomial interpolation.

Conjecture: A function $f(x)$ is a polynomial of degree $n$ if and only if $\forall d\in\mathbb{R}$ there exists a unique polynomial $p(x)$ of degree $n-1$ such that $$\forall x\in\mathbb{R},\quad f(x+d)=f(x)+p(x).$$ Proof sketch: Essentially $p(x)$ is similar to $\frac{d}{dx}f(x)$. If $d>0$, the above formula is similar to the difference quotient. $$\frac{p(x)}{d}=\frac{f(x+d)-f(x)}{d}$$ $$\implies\lim_{d\rightarrow0}\frac{p(x)}{d}=\frac{d}{dx}f(x).$$

If the conjecture is true, take $p(x)=(n+1)^2$ of degree $2$ and $d=1$. Then the conjecture guranatees that $f(x)$ is a polynomial of degree $3$. With initial conditions $f(1)=1)$, $f(2)=5$, $f(3)=14$, and $f(4)=30$, polynomial interpolation yields $f(x)=\frac{x^3}{3}+\frac{x^2}{2}+\frac{x}{6}$ which is the correct sum of squares formula.

Answer 1

Note that $(n+1)^d-n^d =\sum_{k=0}^{d-1} \binom{d}{k} n^k =dn^{d-1}+p_{d-2}(n) $ where $p_{d-2}(n)$ is a polynomial of degree $d-2$.

Therefore, summing from $1$ to $m$,

$\begin{array}\\ \sum_{n=1}^m n^{d-1} &=\frac1{d}\sum_{n=1}^m((n+1)^d-n^d-p_{d-2}(n))\\ &=\frac1{d}\sum_{n=1}^m((n+1)^d-n^d)-\frac1{d}p_{d-2}(n))\\ &=\frac1{a}(m+1)^d-1-\frac1{d}\sum_{n=1}^mp_{d-2}(n)\\ \end{array} $

The induction hypothesis is that the sum of polynomials of degree at most $d-2$ is a polynomial of degree at most $d-1$. Therefore $\sum_{n=1}^mp_{d-2}(n)$ is a polynomial of degree at most $d-1$.

This identity, combined with the fact that any polynomial $q_{d-1}(n)$ of degree $d-1$ can be written as $q_{d-1}(n) =un^{d-1}+q_{d-2}(n)$ where $q_{d-2}(n)$ is a polynomial of at most degree $d-2$, shows that $\sum_{n=1}^m q_{d-1}(n)$ is a polynomial of degree at most $d$.

Answer 2

Assuming

Conjecture: A function $f_m(x)$ is a polynomial of degree $m$ if and only if $\forall d\in\mathbb{R}$ there exists a unique polynomial $p_{m-1}(x)$ of degree $m-1$ such that $$\forall x\in\mathbb{R},\quad f_m(x+d)=f_m(x)+p_{m-1}(x).$$

then

$$ f_m(n+1)=f_m(n)+p_{m-1}(n) $$

but $p_{m-1}(n) = (n+1)^2\Rightarrow m = 3$

so

$$ a_3(n+1)^3+a_2(n+1)^2+a_1(n+1)+a_0 = a_3n^3+a_2n^2+a_1 n+a_0 + (n+1)^2 $$

This should be true for all $n\in \mathbb{N}$ then

$$ \left\{ \begin{array}{rcl} a_1+a_2+a_3-1& =&0 \\ 2 a_2+3 a_3-2& =&0 \\ 3 a_3-1& =&0 \\ \end{array} \right. $$

with solution

$$ a_1 = \frac 16, a_2\frac 12,a_3=\frac 13 $$

Here $a_0$ is determined with the initial condition $f_3(1) = 1$ hence $a_0 = 0$

Answer 3

Assume

$$\sum_{k=0}^n P(k)=Q(n)$$

where $P$ is a polynomial of degree $d$ and $Q$ a polynomial of degree $d+1$.

Then $$P(n)=Q(n)-Q(n-1)=\sum_{i=0}^dq_i(n^i-(n-1)^i)=\sum_{i=0}^dq_iB_i(n)$$ where the $B_i$ are polynomials of degree at most $d$.

If we can find the $d+1$ coefficients $q_i$ by identification, the identity holds for all $n$.

---

For the case of $P(n)=n^2$,

$$q_1+q_2(2n-1)+q_3(3n^2-3n+1)=n^2$$ has the solution

$$q_3=\frac13,\\q_2=\frac12,\\q_1=\frac16,$$ and trivally $q_0=0$.