# Reccurence relation: Lucas sequence

I need to solve the given recurrence relation:$$L_n = L_{n-1} + L_{n-2},$$ $n\geq3$ and $L_1 = 1, L_2 =3$

I'm confused as to what $n\geq3$ is doing there, since $L_1$ and $L_2$ are given I got $t = \frac{1\pm\sqrt 5}{2}$ Which got me the general solution, $L_n = a$(golden ratio)$^n$ + $b$(silver ratio)$^n$

But when I try to plug in numbers and solve from there, the answers don't come out evenly...I feel I'm doing something wrong.

Any help would be appreciated!

-
The "silver ratio" is not the negative of the reciprocal of the golden ratio... –  Ｊ. Ｍ. Jul 12 '12 at 9:32
en.wikipedia.org/wiki/Lucas_number –  PAD Jul 12 '12 at 9:39

$L_n=a(\frac{1+\sqrt 5}{2})^n+b(\frac{1-\sqrt 5}{2})^n$. Putting $n=1$ gives, $$L_1=\frac{a+b}{2}+\frac{(a-b)\sqrt 5}{2}=1$$ and putting $n=2$ gives $$L_2=3\frac{(a+b)}{2}+\frac{(a-b)\sqrt 5}{2}=3$$ $$\implies a+b=2,a=b\implies a=b=1$$ which gives $$L_n=(\frac{1+\sqrt 5}{2})^n+(\frac{1-\sqrt 5}{2})^n$$ Condition $n\geq 3$ is there as the definition of the sequence(that this recurrence is defined for $n\geq 3$).

-
Thank you for your answer. I totally understand this except for the n>=3. I get that the function is undefined at n=1 or n=2, but aren't we using that function to plug in L_1 and L_2? –  pauliwago Jul 12 '12 at 16:42
Function is defined at $n=1,2$(explicitly), recurrence relation is not.In our recurrence relation, we can start putting values only from $n\geq 3$, but the values of function is given at $n=1,2$ explicitly, so we can use it(it is also necessary for the uniqueness of the sequence otherwise, Fibonacci also follows same recursion). –  Aang Jul 12 '12 at 16:52

Combining your formula for $L_n$ with the given values for $L_1$ and $L_2$ gives you:

$$1 = a \left(\frac{1+\sqrt{5}}{2}\right) + b \left( \frac{1-\sqrt{5}}{2}\right)$$

and

$$3 = a \left(\frac{1+\sqrt{5}}{2}\right)^2 + b \left( \frac{1-\sqrt{5}}{2}\right)^2$$

You need to find $a$ and $b$.

-
You will get a slightly simpler system if you use $L_0=a+b$. Since $L_2$ and $L_1$ are given, we have $L_0=L_2-L_1=2$. –  Martin Sleziak Jul 12 '12 at 9:31
I agree, but I wanted to answer the question as stated. I suppose you could substitute $m=n-1$, calculate $a$ and $b$ and then substitute back. –  Chris Taylor Jul 12 '12 at 9:34
But it is not given that $L_0$ is defined, so the trick would be mathematically wrong. Although you can use it here as this is a lucas sequence, which is defined for $n=0$. –  Aang Jul 12 '12 at 9:36
@avatar, but recurrence relations can run backward as well as forward... so the $L_0$ isn't a definition, you can derive it from the initial conditions and the recurrence. –  Ｊ. Ｍ. Jul 12 '12 at 9:49

The identity $L_n=L_{n-1}+L_{n-2}$ holds only for $n \ge 3$ because for $n=1,2$ you would get respectively $L_1=L_0+L_{-1}$ and $L_2=L_1+L_0$ which do not make sense considering the fact that your sequence starts with $L_1$.

After solving the characteristic equation $\lambda^2=\lambda+1$, you should get as solutions $\lambda_1=\frac{1-\sqrt{5}}{2}$ and $\lambda_2=\frac{1+\sqrt{5}}{2}$, therefore $L_n=c_1\lambda_1^n+c_2\lambda_2^n$ for every $n \ge 1$ for some constants $c_1, c_2$. To find theses constants we use the fact that $L_1=1, L_2=3$. Thus $c_1=c_2=1$ and $$L_n=\left(\frac{1-\sqrt{5}}{2}\right)^n+\left(\frac{1+\sqrt{5}}{2}\right)^n \quad \forall\ n \in \mathbb{N}.$$

-

Let $\lambda=\frac{1+\sqrt{5}}{2}$ and $\mu=\frac{1-\sqrt{5}}{2}$. You are right in asserting that there are constants $a$ and $b$ such that $$L_n=a\lambda^n +b\mu^n.\tag{1}$$

To find $a$ and $b$, use the initial conditions. But because we are lazy, we will use a little trick. If we extend the sequence backwards, we see that if the recurrence is to be satisfied, $L_0$ must be $2$. The formula, by general theory, should hold at $n=0$, so we get $a\lambda^0+b\mu^0=2$. It follows that $a+b=2$.

From the fact that $L_1=1$, we find, substituting in $(1)$, that $a\lambda+ b\mu =1$. This gives $$a\left(\frac{1+\sqrt{5}}{2} \right)+b\left(\frac{1-\sqrt{5}}{2} \right)=1.$$ Expand. Already we have $\frac{a}{2}+\frac{b}{2}=\frac{2}{2}=1$. So the part with the $\sqrt{5}$'s must be equal to $0$. That implies that $a-b=0$.

So $a+b=2$ and $a-b=0$, giving $a=b=1$. We conclude that
$$L_n=\lambda^n +\mu^n.$$

Remark: On the confusion about the $n\ge 3$ part: We are told $L_1$ and $L_2$ outright. Then there is the recurrence $L_n=L_{n-1}+L_{n-2}$, for $n \ge 3$. Put in particular $n=3$. That tells us that $L_3=L_2+L_1=4$. Now put $n=4$. That tells us that $L_4=L_3+L_2=7$. And so on forever. The $n \ge 3$ part is because there is no need to assume that the recurrence $L_n=L_{n-1}+L_{n-2}$ holds for $n \lt 3$, since we know $L_1$ and $L_2$.

Actually, the little trick we used to simplify the calculations finds $L_0$, on the assumption that the recurrence holds for $n=2$. And the Lucas sequence can be extended backwards, so that $L_n$ becomes defined for all integers. The formula for $L_n$ that we derived will then hold even for negative $n$.

-