Finding the n'th term of fibonacci like sequence

[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?
Please help. Thank you

 

[jfizzix]

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?
Please help. Thank you

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{<br /> F_{n} \cr <br /> F_{n-1} \cr}<br /> =\pmatrix{<br /> 1 &amp; 1 \cr <br /> 1 &amp; 0 \cr}\pmatrix{<br /> F_{n-1} \cr <br /> F_{n-2} \cr}=\pmatrix{<br /> 1 &amp; 1 \cr <br /> 1 &amp; 0 \cr}^{2}\pmatrix{<br /> F_{n-2} \cr <br /> F_{n-3} \cr}=\pmatrix{<br /> 1 &amp; 1 \cr <br /> 1 &amp; 0 \cr}^{n-2}\pmatrix{<br /> F_{2} \cr <br /> F_{1} \cr}=\pmatrix{<br /> 1 &amp; 1 \cr <br /> 1 &amp; 0 \cr}^{n-2}\pmatrix{<br /> 1 \cr <br /> 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{<br /> 1 &amp; 1 \cr <br /> 1 &amp; 0 \cr}


The eigenvalues of A are \eqalign{<br /> &amp; {\lambda_1} = \frac{1+\sqrt{5}}{2} \cr <br /> &amp; {\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{<br /> \lambda_{1} &amp; 0 \cr <br /> 0 &amp; \lambda_{2} \cr} is a diagonal matrix,

\Lambda^{n}=\pmatrix{<br /> \lambda_{1}^{n} &amp; 0 \cr <br /> 0 &amp; \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.

 

[Office_Shredder]

Another method that has a less challenging end step to do by hand is the following (again for the Fibonnaci sequence). Suppose that H_n = xⁿ for some x, and H_n = H_n-1 + H_n-2. Then
x^n = x^{n-1} + x^{n-2}
for all n. Divide both sides by x^n-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 H_n = H_n-1 + H_n-2 is linear, i.e. if X_n and Y_n satisfy it, and a and b are numbers, aX_n+bY_n satisfies it as well. So H_n 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 H_n to be the Fibonacci sequence, then H₁ = H₂ = 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 F_n (actually I think your formula is missing a minus sign).

You can do the same procedure for your G_n - 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 G_n 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 G_n for really large values of n.

 

[jfizzix]

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

For this problem we diagonalize the matrix
B=\pmatrix{<br /> 1 &amp; 0 &amp; 1 \cr <br /> 1 &amp; 0 &amp; 0 \cr<br /> 0 &amp; 1 &amp; 0 \cr}

Which comes into play as:

\pmatrix{<br /> G_{n} \cr <br /> G_{n-1} \cr<br /> G_{n-2} \cr} = \pmatrix{<br /> 1 &amp; 0 &amp; 1 \cr <br /> 1 &amp; 0 &amp; 0 \cr<br /> 0 &amp; 1 &amp; 0 \cr}\pmatrix{<br /> G_{n-1} \cr <br /> G_{n-2} \cr<br /> G_{n-3} \cr} =\pmatrix{<br /> 1 &amp; 0 &amp; 1 \cr <br /> 1 &amp; 0 &amp; 0 \cr<br /> 0 &amp; 1 &amp; 0 \cr}^{n-3}\pmatrix{<br /> G_{3} \cr <br /> G_{2} \cr<br /> G_{1} \cr}=\pmatrix{<br /> 1 &amp; 0 &amp; 1 \cr <br /> 1 &amp; 0 &amp; 0 \cr<br /> 0 &amp; 1 &amp; 0 \cr}^{n-3}\pmatrix{<br /> 1 \cr <br /> 1 \cr<br /> 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.