Creating a formula for $a_n$ for a Fibonacci like sequence

This is sequence is "Fibonacci like":

$$t_1, t_2, t_1+t_2, t_1+2t_2,...$$ How can I find the $$1001^{st}$$ term of this sequence.

I'm a littler confused because this sequence is neither arithmetic nor geometric so I'm a little confused as to how to solve these problems. I know the Fibonacci sequence and the way to find the numbers for that are:

$$f_n=f_{n-1}+f_{n-2}$$ and $$f_0=1$$ and $$f_1=1$$

How could I approach this problem?

• 997 more steps and you will have term 1001 .i have never seen an easier way . – StuartMN May 19 at 6:12

This amounts to solving the recurrence relation

$$T_1 = t_1, \qquad T_2 = t_2, \qquad T_{n+2} = T_{n+1} + T_n.$$

By linearity, we may write $$T_n = A_n t_1 + B_n t_2$$, where $$A_n$$ and $$B_n$$ are sequences defined by the following recurrence relations.

$$A_1 = 1, \qquad A_2 = 0, \qquad A_{n+2} = A_{n+1} + A_n, \\ B_1 = 0, \qquad B_2 = 1, \qquad B_{n+2} = B_{n+1} + B_n.$$

It is easy to check that $$A_n = F_{n-2}$$ and $$B_n = F_{n-1}$$ solve these, where $$F_n$$ is the Fibonacci number starting with $$F_1 = F_2 = 1$$. So

$$T_n = t_1 F_{n-2} + t_2 F_{n-1}.$$

The followings are first 10 values of $$T_n$$.

\begin{align*} \begin{array}{|c|c|} \hline n & T_n \\ \hline 1 & t_1 \\ 2 & t_2 \\ 3 & t_1+t_2 \\ 4 & t_1+2 t_2 \\ 5 & 2 t_1+3 t_2 \\ 6 & 3 t_1+5 t_2 \\ 7 & 5 t_1+8 t_2 \\ 8 & 8 t_1+13 t_2 \\ 9 & 13 t_1+21 t_2 \\ 10 & 21 t_1+34 t_2 \\ \hline \end{array} \end{align*}

• sorry i'm just a little confused about what $A_n$ and $B_n$ are and if you chose what values to attribute to them – user130306 May 19 at 7:05
• @user130306, I added a few more words. – Sangchul Lee May 19 at 7:09
• thanks, that helps a lot. but the values of $A_1, A_2, B_1, B_2$ is just something you know to make work for the recurrence relation? basically, my question is how would i know to pick those values for $A_1, B_1, ..$ etc. or define those sequences in that specific way – user130306 May 19 at 7:11
• also when you say $A_n = F_{n-2}$ am i supposed to be able to recognize this just based off the values for $F_1, F_2,...$ or is there a certain way you solved it – user130306 May 19 at 7:13
• @user130306, The basic motivation comes from the fact that solutions of the recurrence relations $a_{n+2} = a_{n+1} + a_n$ form a vector space of dimension 2, and so, any solution can be written as a linear combination of two linearly independent solutions. I simply chose a specific linearly independent solutions so that they are easy to work with. And for your second question, I simply recognized the relation $A_n = F_{n-1}$ solely based on the known values of $F_n$'s. In general we do not expect this happy coincidence. – Sangchul Lee May 19 at 7:32

You look for $$r_1, r_2$$ roots of $$X^2-X-1$$, and $$\lambda, \mu$$ such that $$\lambda+\mu=t_1, \lambda.r_1+\mu.r_2=t_2$$.

Then you can easily prove that the $$n$$-th term of the sequence is given by: $$\lambda.r_1^n + \mu.r_2^n$$

From the third term we may find this pattern,

$$T_3 = t_1 + t_2 = t_1 + (3-2)t_2$$

$$T_4 = t_1 + t_3 = t_1 + (4-2)t_2$$

If the pattern continues for all consequent terms, then

$$T_n = t_1 + (n-2)t_2$$

So this may be the general $$n^{th}$$ term.

$$T_{1001} = t_1 + 999t_2$$

• oh wow that seems simple enough, thanks for such a concise explanation. If i wanted to find the sum of this series, there's no formula right? what kind of series is this if it isn't geometric or arithmetic? – user130306 May 19 at 6:21
• Have you compared your formula with the actual value of $T_5$? – Sangchul Lee May 19 at 6:37
• @user130306 The answer of Sangchul Lee fits the best. So kindly accept his and un-accept mine. – Ak19 May 19 at 6:45
• @SangchulLee Sorry, I didn't see it. I just thought it to be an arithmetic progression from the third term. – Ak19 May 19 at 6:49