This is a question where I was given the solution sometime in high school, but had forgotten about over the years. Given that I have an ample amount of free time, I thought I might give this question a tackle for the sake of keeping my mind active.

Defining the problem

The Fibonacci sequence , with the recurrence relation is famously known for generating the Golden ratio .

But the generation of the golden ratio is not unique to this particular starting point of the Fibonacci sequence. In fact, even if you decide to start out with different first and second terms, the Golden ratio still appears in the generated integers.

It should be that the result of having the Golden ratio appear is more related to the recurrence relation itself rather than the specific sequence itself. With a different recurrence relation, we should expect different ratios to appear in the resulting sequence.

So our generalized question is as followed: Given the recurrence relation

Can we find the closed-form expression of ?

The general strategy

We attempt to require the recurrence relation into one that we already know how to solve: a simple geometric sequence. In particular, we attempt to find so that we can write the recurrence relation as a geometric sequence of :

Explicitly writing this out in terms of the original recurrence relation:

For the second equation to be a simple geometric sequence, we can see that is restricted to the root of the equation:

The coefficients in the original recurrence relations define a characteristic equation for . Here we need to take into account that the characteristic equation could have repeated roots. But let’s first tackle the one without repeated roots first.

Solution with unique roots

Given the two roots , , we know have two geometric equation that could be used to rewrite our original recurrent relation:

The closed form of the sequence for and could then be written as:

It might feel a bit fishy writing , but one can simply view it as a continuation of the sequence in the negative direction while keeping the recurrence relation. For example, in the case of the Fibonacci sequence, we can include the negative terms into something like: . Or, you can of course simple shift the dependence on to be something like . In any case, you can think of and as constants determined by the initial terms of the sequence, independent of the actual recurrence relation. After solving the closed form of and , we could solve using simple algebra to eliminate the dependence for :

In our special case of the Fibonacci sequence with , , . The characteristic equation is given as:

Taking in these numbers into the general solution above, we get the relation:

or

Which is what we find on wikipedia! The relation here with the golden ratio is also make apparent in the closed form, as , asymptotically the Fibonacci sequence approaches a geometric sequence with a ratio of .

Solution with the repeated roots.

In the case that the coefficients in the recurrence relation satisfies the relation: , then the characteristic equation has repeated roots of , we are left with the single extended sequence:

the solution is to further decouple from , after already knowing that , is make the assumption that , then the relation between and could be rewritten as:

Again, is some constant to be determined by the initial terms of . The recurrence relation for is such that it is at most an arithmetic sequence, in other words: . So the closed form of is: