1

$Q$ is a function from $\mathbb N$ to itself, $Q(n)-Q(n-1)=T(n)$ where $T$ is some polynomial of degree $k$. Prove that $Q$ is a polynomial of degree $k+1$.

I've been given the above problem in an "elementary mathematics" course problem set. I've shown that $Q(n)=T(n)+T(n-1)+...T(1)+Q(0)$ (I'm including $0$ in the naturals) but that doesn't seem to clarify things. I know I can construct a polynomial $P$ of degree $k+1$ such that $P(n)=Q(n)$ for $0\leq n \leq k+1$ but I couldn't show that it is equal for all other numbers. Other than those attempts I don't know how to proceed, I can't think up other ways to show that a function is a polynomial other than explicitly constructing one that fits. Help would be appreciated.

Mohsen Shahriari
  • 6,718
Adgorn
  • 367
  • 1
    Summing a polynomial results in a polynomial of one degree higher. See e.g. https://en.wikipedia.org/wiki/Faulhaber%27s_formula or https://math.stackexchange.com/questions/654765/sum-of-polynomial. – Minus One-Twelfth Aug 11 '20 at 21:10
  • 2
    Does this answer your question? Sum of polynomial – Somos Aug 11 '20 at 21:19
  • @Somos Evidently it does however it seems a bit too complex for what would be expected from me. This is part of a problem set in a "concepts in elementary mathematics" course so I wonder if there isn't a simpler way to go about this. – Adgorn Aug 11 '20 at 21:28
  • Please give this information in the question body so that the appropriate level of context is known and that the answers can apply to your situation. – Somos Aug 11 '20 at 21:54

1 Answers1

2

A simple way to think about this problem of polynomial summation is to use binomial coefficients. Consider the sequence of polynomial functions $\,C_m(n) := \binom{n}{m} \,$ which map $\,\mathbb{N}\,$ to $\,\mathbb{N}\,$. They have the properties that $\,C_m(n)-C_m(n-1) = C_{m-1}(n-1),\,$ $\,C_m(n)\,$ is of degree $\,m,\,$ and $\,C_m(n) = 0\,$ if $\,0\le n<m.\,$ Notice that given any polynomial function $\,f: \mathbb{N}\to\mathbb{N},\,$ the properties can be used to prove that $\,f(n)\,$ can be expressed as a sum of binomial coefficients and thus to express the partial sums of $\,f(n)\,$ as a corresponding sum of binomial coefficients.

For example, suppose $\,f(n) = \sum_{m\in\mathbb{N}} a_m\,C_m(n).\,$ Then $\,a_0 = f(0) \in\mathbb{N}\,$ using the $3$rd property. Now, similarly we can show that $\,a_1 = f(1)-f(0)\in\mathbb{Z}.\,$ In general, the coefficients $\,a_m = \Delta^mf(n)|_{n=0}\in\mathbb{Z}\,$ are the entries in the difference table of $\,f(n)\,$ at $\,n=0.$

For your situation, let $\,f(n)=Q(n)-Q(n-1)=T(n)\,$ where $\,T\,$ is of degree $\,k\,$ which implies that $\,Q(n)= Q(0) + \sum_{m=0}^k a_{m+1}\,C_{m+1}(n+1)\,$ which is of degree $\,k+1.$

Somos
  • 35,251
  • 3
  • 30
  • 76