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?

  • $\begingroup$ 997 more steps and you will have term 1001 .i have never seen an easier way . $\endgroup$
    – StuartMN
    May 19 '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*}

  • $\begingroup$ 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 $\endgroup$
    – user130306
    May 19 '19 at 7:05
  • $\begingroup$ @user130306, I added a few more words. $\endgroup$ May 19 '19 at 7:09
  • $\begingroup$ 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 $\endgroup$
    – user130306
    May 19 '19 at 7:11
  • $\begingroup$ 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 $\endgroup$
    – user130306
    May 19 '19 at 7:13
  • 1
    $\begingroup$ @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. $\endgroup$ May 19 '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$

  • $\begingroup$ 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? $\endgroup$
    – user130306
    May 19 '19 at 6:21
  • $\begingroup$ Have you compared your formula with the actual value of $T_5$? $\endgroup$ May 19 '19 at 6:37
  • $\begingroup$ @user130306 The answer of Sangchul Lee fits the best. So kindly accept his and un-accept mine. $\endgroup$
    – Ak.
    May 19 '19 at 6:45
  • $\begingroup$ @SangchulLee Sorry, I didn't see it. I just thought it to be an arithmetic progression from the third term. $\endgroup$
    – Ak.
    May 19 '19 at 6:49

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.