Prove certain recursive functions are polynomials 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.
 A: 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$
A: 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$.
A: 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$.
