# Prove that a sequence whose second difference is a nonzero constant is quadratic.

For example, if {$a_0, a_1, a_2, a_3, ...$} is the sequence, the first difference is {$a_1-a_0, a_2-a_1, a_3-a_2, ...$}, and the second difference is {$(a_2-a_1)-(a_1-a_0), (a_3-a_2)-(a_2-a_1), ...$}.

I think that using facts from up to Calculus, perhaps derivatives, should be enough. I find myself going in circles and don't know how to approach this.

• It would help to define what "second common difference" means for a sequence. – Michael Aug 12 '15 at 23:22
• It may also help to state the context, is this a homework problem? What have you tried? – Michael Aug 12 '15 at 23:24
• You did not provide a definition. After a web search, it seems that "second difference is constant" might refer to a sequence $\{a_n\}_{n=0}^{\infty}$ that satisfies $(a_{n+2}-a_{n+1})-(a_{n+1}-a_n) = c$. This is a simple linear difference equation and has a standard solution that is indeed quadratic regardless of initial conditions for $a_0, a_1$. I suspect this is a homework problem. – Michael Aug 12 '15 at 23:36
• @Michael. He's talking about the Calculus of finite differences. – steven gregory Aug 13 '15 at 0:50
• @Michael I got $a_n = \frac{d}{2}n^2+(a_1-a_0-\frac{d}{2})n+a_0$, where $d$ is the second difference. Now I just need to prove it satisfies the criteria? – VirtualBen Aug 14 '15 at 1:23

## 1 Answer

Let $d$ denote the constant second difference. Moreover, let \begin{align*} c\equiv&\,a_1-a_0-\frac{d}{2},\\ \end{align*}

Claim: $a_n=(d/2)n^2+cn+a_0$ for all $n\in\{0,1,2\ldots\}$.

Proof: The claim is obviously true for $n=0$. For $n=1$, $$\frac{d}{2}\times n^2+cn+a_0=\frac{d}{2}+\left(a_1-a_0-\frac{d}{2}\right)+a_0=a_1.$$ Proceed by induction: suppose that the claim is true for $0,1,\ldots,n$ for some integer $n\geq1$. The task is to prove that it is true for $n+1$. Now: \begin{align*} d=&\,(a_{n+1}-a_n)-(a_n-a_{n-1})=a_{n+1}-2a_n+a_{n-1}\\ =&\,a_{n+1}-2\left[\frac{d}{2}\times n^2+cn+a_0\right]+\left[\frac{d}{2}\times (n-1)^2+c(n-1)+a_0\right], \end{align*} where the first equality comes from the definition of $d$, and the third one is due to the induction hypothesis. Now, rearrange for $a_{n+1}$: \begin{align*} a_{n+1}=&\,d+2\left[\frac{d}{2}\times n^2+cn+a_0\right]-\left[\frac{d}{2}\times (n-1)^2+c(n-1)+a_0\right]\\ =&\,d+dn^2+2cn+2a_0-\frac{d}{2}\times(n^2-2n+1)-c(n-1)-a_0\\ =&\,\underbrace{d}_{\spadesuit}+\underbrace{dn^2}_{\heartsuit}+\underbrace{2cn}_{\clubsuit}+\underbrace{2a_0}_{\diamondsuit}-\underbrace{\frac{d}{2}\times n^2}_{\heartsuit}+\underbrace{dn}_{\star}-\underbrace{\frac{d}{2}}_{\spadesuit}-\underbrace{cn}_{\clubsuit}+\underbrace{c}_{\clubsuit}-\underbrace{a_0}_{\diamondsuit}\\ =&\,\underbrace{\frac{d}{2}}_{\spadesuit}+\underbrace{\frac{d}{2}\times n^2}_{\heartsuit}+\underbrace{c(n+1)}_{\clubsuit}+\underbrace{a_0}_{\diamondsuit}+\underbrace{dn}_{\star}\\ =&\,\frac{d}{2}\times n^2+dn+\frac{d}{2}+c(n+1)+a_0\\ =&\,\frac{d}{2}\times(n+1)^2+c(n+1)+a_0. \end{align*} The proof is complete. $\quad\blacksquare$

• For some reason, now I want to go play poker. =) – Michael Aug 14 '15 at 7:08
• Super! Should I use induction to show that if the third difference of a sequence is a nonzero constant, then the sequence is polynomial of 3rd degree? What about proving that if the nth difference of a sequence is a nonzero constant, then the sequence is polynomial of nth degree? – VirtualBen Aug 14 '15 at 19:15
• @VirtualBen I think that would work, but the algebra gets increasingly tedious as the number of degrees grows. Suppose the $k$th difference (where $k\in\mathbb N)$ is constant and you want to show that $$a_n=\sum_{j=0}^k\beta_j n^j\tag{\clubsuit}$$ for all integers $n\geq0$, where the $\beta_0,\ldots,\beta_k$ are constants to be found. In general, $\beta_j$ (where $j\in\{0,\ldots,k-1\}$) would depend on $a_0,\ldots,a_j$, and you would need to check that ($\clubsuit$) holds “by hand” for $n\in\{0,\ldots,k-1\}$. Then, for $n\geq k-1$, you could check if the induction goes through for $n+1$. – triple_sec Aug 15 '15 at 0:16
• @VirtualBen This reminds me of the following fact: Suppose that the function $f:\mathbb R\to\mathbb R$ is differentiable $k\in\mathbb N\cup\{0\}$ times. Then, $f$ is a polynomial of degree at most $k$ if and only if the $k$th derivative $f^{(k)}$ is a constant function. Moreover, it is a polynomial of degree precisely $k$ if and only if $f^{(k)}$ is a non-zero constant function. – triple_sec Aug 15 '15 at 0:21
• This analog to calculus was exactly what I was thinking at first. Except I don't know exactly how the derivative for a function $\mathbb{R} \rightarrow \mathbb{R}$ translates to a difference of a sequence. – VirtualBen Aug 15 '15 at 0:43