Finding the n'th term of fibonacci like sequence

lundi 30 septembre 2013

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