Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I got a particular sequence defined by the following recursive function: $$T_n = T_{n-1} \times 2 - T_{n-10}$$

I need help converting it to a closed form so I can calculate very large values of n efficiently.

The sequence that I produced this recursive formula from is:

n = 1 to 10: 1,1,2,4,8,16,32,64,128,256

n = 11 to 15: 511,1021,2040,4076,8144

The formula is "quirky" for 1 to 10, but works exactly as stated for all n > 10;

share|cite|improve this question

ok. There is a general way to solve linear recursions as yours, see for starting the Wikipedia article. The basic idea is to look for solutions of the form $T_n = \lambda^n$. Inserting this ansatz into the equation we obtain $$ \lambda^n = 2\lambda^{n-1} - \lambda^{n-10} $$ and after dividing by $\lambda^{n-10}$ $$ \lambda^{10} - 2\lambda^9 + 1 = 0 $$ Now you have to find all $\lambda_i$, $i = 1,\ldots, 10$ which solve this equation. Wolfram|Alpha helps. Now one can show, that $\{(\lambda_i^n)_{n\ge 0}\mid 1 \le i \le 10\}$ is a basis of the space of all sequences which fulfill your recursion. Now we put your initial values into the ansatz $T_n = \sum_{i=1}^{10} a_i \lambda_i^n$. We obtain (with $\lambda_1 = 1$) \begin{align*} a_1 + a_2\lambda_2 + a_3\lambda_3 + \cdots + a_{10}\lambda_{10} &= 1\\\ a_1 + a_2\lambda_2^2 + a_3\lambda_3^2 + \cdots + a_{10}\lambda_{10}^2 &= 1\\\ \vdots &= \vdots\\\ a_1 + a_2 \lambda_2^{9} + a_3 \lambda_3^{9} + \cdots + a_{10}\lambda_{10}^{9} &= 128\\\ a_1 + a_2 \lambda_2^{10} + a_3 \lambda_3^{10} + \cdots + a_{10}\lambda_{10}^{10} &= 256 \end{align*} a linear system for $a_1, \ldots, a_{10}$. You have to solve this for $a_1, \ldots, a_{10}$.

The problem is, as suggested by Wolfram|Alpha, the roots of your equation besides $\lambda_1 = 1$ are diffucult, if not ipossible, to write in closed form.

Hope this helps,

share|cite|improve this answer
Thank you. It is exactly as you say, I can only get approximate roots to the characteristic equations which makes the closed formula very inaccurate. – Kal Apr 13 '12 at 6:31

For what it's worth, $$T_n = 2^n - 2^{n-10} \sum _{k = 0} ^{\lfloor \frac n 9 - 1 \rfloor} \binom {n-9k-8} {k+1} 2^{-10k} (-1)^k \frac {n-8k-7} {n-9k-8}$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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