Let's consider a difference operator $\triangle f(n)= f(n+1)-f(n)$. How to prove that $f$ is a polynomial so that $deg(f) \leq d$ if and only if $\triangle f ^{d+1} =0$.
First step of the solution might be like this: $\triangle ^{d+1} f(n)= \binom {d+1}{0} f(n+d+1)- \binom {d+1}{1} f(n+d) + \binom {d+1}{2} f(n+d-1)- \ldots - \binom {d+1}{2} f(n+1)+ \binom {d+1}{1} f(n) $, but i have no reasonable ideas about how to work with it.
The hardest part is to show the inverse statement: if $f$ satisfies this condition, so it's a polynomial.
Could somebody give me a hint?
Let $\displaystyle f(x) = \sum_{i=0}^n a_i x^i$.
$\displaystyle \Delta f(x) = f(x+1) - f(x) = \sum_{i=0}^n a_i (x+1)^i - \sum_{i=0}^n a_i x^i = a_i x^n + o(x^{n-1}) - a_i x^n + o(x^{n-1}) = o(x^{n-1})$
and therefore $\operatorname{deg} \Delta f \leq \operatorname{deg} f - 1$.
By induction you get that $\operatorname{deg} \Delta^{d+1} f \leq \operatorname{deg} f - (d+1)$.
If $\operatorname{deg} f \leq d$ then $\operatorname{deg} \Delta^{d+1} f \leq -1$ so $\Delta^{d+1} f = 0$.
For the inverse statment I'm not sure if you can prove that $f$ must be a polynomial, but if it is a polynomial then it is easy to prove that $\operatorname{deg} f \leq d$.
We prove the contrapositive:
suppose $\Delta^{d+1} f \neq 0$, then $\operatorname{deg} \Delta^{d+1} f \geq 0$ and therefore $\operatorname{deg} f \geq \operatorname{deg} \Delta^{d+1} f + (d+1) \geq d + 1$, which is equivalent to $\operatorname{deg} f > d$.