5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ It would help to define what "second common difference" means for a sequence. $\endgroup$ – Michael Aug 12 '15 at 23:22
  • $\begingroup$ It may also help to state the context, is this a homework problem? What have you tried? $\endgroup$ – Michael Aug 12 '15 at 23:24
  • $\begingroup$ 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. $\endgroup$ – Michael Aug 12 '15 at 23:36
  • $\begingroup$ @Michael. He's talking about the Calculus of finite differences. $\endgroup$ – steven gregory Aug 13 '15 at 0:50
  • 1
    $\begingroup$ @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? $\endgroup$ – VirtualBen Aug 14 '15 at 1:23
2
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ For some reason, now I want to go play poker. =) $\endgroup$ – Michael Aug 14 '15 at 7:08
  • 1
    $\begingroup$ 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? $\endgroup$ – VirtualBen Aug 14 '15 at 19:15
  • $\begingroup$ @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$. $\endgroup$ – triple_sec Aug 15 '15 at 0:16
  • 1
    $\begingroup$ @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. $\endgroup$ – triple_sec Aug 15 '15 at 0:21
  • $\begingroup$ 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. $\endgroup$ – VirtualBen Aug 15 '15 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.