# Finding the n'th term of fibonacci like sequence

1. Sep 30, 2013

### neerajareen

The fibonacci sequence can be defined as $${F_n} = {F_{n - 1}} + {F_{n - 2}}$$ ￼and specifying the initial conditions as \eqalign{ & {F_1} = 1 \cr & {F_2} = 1 \cr}

Also there exists a general formula for the fibonacci which is given by $${F_n} = {{{\varphi ^n} + {\psi ^n}} \over {\sqrt 5 }}$$

Where ￼$$\varphi = {{1 + \sqrt 5 } \over 2}$$ and $$\psi = {{1 - \sqrt 5 } \over 2}$$ ￼.
Ι understand that the derivation of the formula was obtained using generating functions.
My question is that supposing we have a new sequence defined to be $${G_n} = {G_{n - 1}} + {G_{n - 3}}$$ ￼and the initial conditions being:
\eqalign{ & {G_1} = 1 \cr & {G_2} = 1 \cr & {G_3} = 1 \cr}

What’s the formula for the n’th term in the sequence. The generating function for the function is going to be

$$A(x) = {x \over {1 - x - {x^3}}}$$

￼. But due to the imaginary roots that are present, I am not able to use the method of partial fractions.
Can this method still be used or is there any other method that we can use to get the n’th number of this sequence?

2. Sep 30, 2013

### jfizzix

This kind of problem can also be solved with linear algebra. I'll demonstrate with the Fibonnacci problem.

Let $F_{n}$ be the nth term in the Fibonnacci series so that
$F_{n}=F_{n-1}+F_{n-2}$.

Using the identity
$F_{n-1}=F_{n-1}$,
we can express the iteration from one term to the next as a matrix multiplication

$\pmatrix{ F_{n} \cr F_{n-1} \cr} =\pmatrix{ 1 & 1 \cr 1 & 0 \cr}\pmatrix{ F_{n-1} \cr F_{n-2} \cr}=\pmatrix{ 1 & 1 \cr 1 & 0 \cr}^{2}\pmatrix{ F_{n-2} \cr F_{n-3} \cr}=\pmatrix{ 1 & 1 \cr 1 & 0 \cr}^{n-2}\pmatrix{ F_{2} \cr F_{1} \cr}=\pmatrix{ 1 & 1 \cr 1 & 0 \cr}^{n-2}\pmatrix{ 1 \cr 1 \cr}$

Solving for $F_{n}$ then boils down to figuring out a formula for the nth power of a 2x2 matrix.

Let $A=\pmatrix{ 1 & 1 \cr 1 & 0 \cr}$

The eigenvalues of $A$ are \eqalign{ & {\lambda_1} = \frac{1+\sqrt{5}}{2} \cr & {\lambda_2} = \frac{1-\sqrt{5}}{2} \cr}

We can diagonalize $A$ , so that it has the form
$A= U \Lambda U^{-1}$
where $\Lambda=\pmatrix{ \lambda_{1} & 0 \cr 0 & \lambda_{2} \cr}$ is a diagonal matrix,

$\Lambda^{n}=\pmatrix{ \lambda_{1}^{n} & 0 \cr 0 & \lambda_{2}^{n} \cr}$.

Since $U U^{-1} = U^{-1} U = I$,
we have that
$A^{n}= U \Lambda^{n} U^{-1}$

Knowing that you get $U$ from the diagonalization, you have all the information you need to complete the matrix multiplication to find $F_{n}$.

I believe you will find this procedure to work nicely for your problem, though it's a little more challenging to diagonalize a 3x3 matrix.

3. Sep 30, 2013

### Office_Shredder

Staff Emeritus
Another method that has a less challenging end step to do by hand is the following (again for the Fibonnaci sequence). Suppose that Hn = xn for some x, and Hn = Hn-1 + Hn-2. Then
$$x^n = x^{n-1} + x^{n-2}$$
for all n. Divide both sides by xn-2 and we get
$$x^2 = x+1$$
$$x^2 - x -1 = 0$$
which of course has roots $(1\pm \sqrt{5})/2$. The relation Hn = Hn-1 + Hn-2 is linear, i.e. if Xn and Yn satisfy it, and a and b are numbers, aXn+bYn satisfies it as well. So Hn can be anything of the form
$$H_n = a \left(\frac{1+\sqrt{5}}{2}\right)^n + b\left(\frac{1-\sqrt{5}}{2} \right)^n$$
where a and b are any numbers. If we want Hn to be the Fibonacci sequence, then H1 = H2 = 1 - these give you two equations and two unknowns (a and b) which allow you to solve for a and b, and gives you that formula for Fn (actually I think your formula is missing a minus sign).

You can do the same procedure for your Gn - you'll get three roots because you will be left with a cubic equation, so you'll have three unknowns which makes sense because the first three values of Gn will have to be specified. Unless you have a closed form expression for your roots though you will have some floating point issues if you try to use this to evaluate Gn for really large values of n.

4. Oct 1, 2013

### jfizzix

Maybe diagonalizing a 3x3 matrix in this case wouldn't be so bad.

For this problem we diagonalize the matrix
$B=\pmatrix{ 1 & 0 & 1 \cr 1 & 0 & 0 \cr 0 & 1 & 0 \cr}$

Which comes into play as:

$\pmatrix{ G_{n} \cr G_{n-1} \cr G_{n-2} \cr} = \pmatrix{ 1 & 0 & 1 \cr 1 & 0 & 0 \cr 0 & 1 & 0 \cr}\pmatrix{ G_{n-1} \cr G_{n-2} \cr G_{n-3} \cr} =\pmatrix{ 1 & 0 & 1 \cr 1 & 0 & 0 \cr 0 & 1 & 0 \cr}^{n-3}\pmatrix{ G_{3} \cr G_{2} \cr G_{1} \cr}=\pmatrix{ 1 & 0 & 1 \cr 1 & 0 & 0 \cr 0 & 1 & 0 \cr}^{n-3}\pmatrix{ 1 \cr 1 \cr 1 \cr}$

but then, you'd still have to solve a cubic equation
$\lambda^{3}-\lambda^{2}-1=0$
to find the eigenvalues. There are no rational roots to this equation, so solving it on paper without a copy of the cubic formula would be a challenge. A fun challenge.