1
$\begingroup$

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;

2 Answers 2

3

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,

  • 0
    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.2012-04-13
2

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}$