Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Predict next number from a series

I gave wolfram alpha the sequence: $1,3,13,31,57,91,133,183,241$ and it told me a possible closed form would be $4n^2 -10n + 7$ (which turned out to be right for where I was getting the sequence from). What are some ways of doing this given some terms? I have seen recurrences being approached with power series to find generating functions, but don't recall seeing methods for going from some terms into a possible closed form. What are some approaches?

share|improve this question
2  
For the specific problem of finding a low-degree polynomial, take finite differences until the finite differences appear constant. For the general problem, it depends very strongly on what kind of rule you expect to generate the sequence. –  Qiaochu Yuan May 27 '12 at 3:44
add comment

marked as duplicate by Gerry Myerson, tomasz, Chris Eagle, sdcvvc, William Aug 29 '12 at 21:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

up vote 4 down vote accepted

To expand on Qiaochu Yuan's comment let us take finite differences until the finite differences appear constant.

$$\begin{array}{|c|c|c|} a_n & b_n &c_n \\ \hline 1 \\ \hline &3-1=2\\ \hline 3&&10-2=8 \\ \hline & 13-3=10\\ \hline 13&&18-10=8 \\ \hline &31-13=18\\ \hline 31&&26-18=8 \\ \hline &57-31=26\\ \hline 57 \\ \hline \end{array}$$ I.e. Let $a_n$ be the sequence in question. Let $b_n$ be the difference between two consecutive terms in $a_n$ and let $c_n$ be the difference between two consecutive terms in $b_n$. Working backwards we get that $$\begin{align*}b_n&=b_1+\sum_{k=1}^{n-1}c_k \\ a_n&=a_1+\sum_{k=1}^{n-1}b_k\end{align*}$$ Since $c_n=8$ and $b_1=2$ $$b_n=b_1+\sum_{k=1}^{n-1}c_k=2+\sum_{k=1}^{n-1}8=2+8(n-1)=8n-6$$ Finally, using $b_n$ we can find $a_n$ $$a_n=a_1+\sum_{k=1}^{n-1}b_k=1+\sum_{k=1}^{n-1}(8k-6)=1+8\sum_{k=1}^{n-1}k-\sum_{k=1}^{n-1}6$$ $$=1+8\left(\frac{(n-1)(1+n-1)}{2}\right)-6(n-1)=4(n^2-1)-6n+7=\fbox{$4n^2-10n+7$}$$

share|improve this answer
    
Thank you, very detailed response. –  Palace Chan May 28 '12 at 0:50
add comment

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