4
$\begingroup$

Yesterday, I was pondering on the Fibonacci sequence and I started to discover some features of it that were previously unknown to me. Such as,

1, 1, 2, 3, 5, 8, 13, 21, 34 ....

1 ) The nth element of the sequence is the sum-1 of first n-2 elements. 2) If you multiply the first number with one and the second one with the two and sum them, you would get the fibonacci number, after the next element of the sequence. For example, 1x1 + 1x2 = 3. 3x1 + 5x2 = 13. 5x1 + 8x2 = 21. and so on. What is more, if I do this for another subsequent (5, 8 or 2, 3) fibonacci numbers I would get another Fibonacci number but in this case, I would not skip one element, instead, I would skip 'x' times where 'x' is equal to the index of the first occurence of the subsequent numbers.

For example, 3x5 + 5x8 = 55, normally we would get the next element, if the second operands would be one but in this case we get the 4th element after the next fibonacci number.

It amazed me and I asked to myself, if there was any other such sequence.

Then I realized that, any sequence generated by random two number has the same property. For example, suppose that the first two numbers in my sequence are 3 and 4. I will generate the next element of the sequence by multiplying the previous one with 3, the current one with 4 and summing those two results.

Following happens,

3, 4, 25, 112, 523 ...

And this series also satisfies the second property mentioned above.

So, my question is, Do all this sort of sequences have another name which refers to that abstraction? OR is this property trivial?

$\endgroup$
1
  • 3
    $\begingroup$ $x_n\cdot 1 + x_{n+1}\cdot 2 = (x_n+x_{n+1}) + x_{n+1}=x_{n+2}+x_{n+1}=x_{n+3}$ $\endgroup$
    – parsiad
    Apr 7, 2015 at 17:05

2 Answers 2

Reset to default
2
$\begingroup$

I think you should take a look at recurrence relations - wikipedia has a nice article on them.

The Fibbonacci sequence is given by such a relation:

$$f_{n+2}=f_{n+1}+f_{n},\quad f_0=f_1=1.$$ This definition directly yields you second property: $f_{n+3}=f_{n+2}+f_{n+1} = 2f_{n+1}+f_{n}$. This a particular case of linear recurrence relation of second order (an element is a linear combination of two its predecessors).

In general case the second order linear homogenous relation writes $$x_{n+2} = ax_{n+1}+bx_n$$ with some sort of initial data. These relations are useful, for example, for finding the determninants of tridiagonal matrices (if the determinant is non-zero then we have nonzero eigenvalues), which in turn arise quite often in numerical methods (recall the matrix of discretised second order derivative).

The homogenous first order recurrence relations yield geometric progressions: $x_{n+1}=ax_n$.

$\endgroup$
1
$\begingroup$

As @TZakrevskiy points out, what you describe is $$ x_{n}=x_{1}x_{n-1}+x_{0}x_{n-2}\text{ for }n>1. $$ Let $$ \mu_{\pm}=x_{1}\pm\sqrt{x_{1}^{2}+4x_{0}}. $$ This recurrence can be solved to yield $$ x_{n}=\frac{1}{2^{n+1}}\left[\frac{x_{1}\left(x_{0}-2\right)}{\sqrt{x_{1}^{2}+4x_{0}}}\left(\mu_{-}^{n}-\mu_{+}^{n}\right)+x_{0}\left(\mu_{-}^{n}+\mu_{+}^{n}\right)\right] $$

$\endgroup$
1
  • 1
    $\begingroup$ You can verify that for $x_0=3,x_1=4$, the first terms are $3,4,25,112,523,2428,11281,52408,\ldots$ $\endgroup$
    – parsiad
    Apr 7, 2015 at 17:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .