1
$\begingroup$

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!

  • 0
    http://en.wikipedia.org/wiki/Lucas_number2012-07-12

4 Answers 4

3

$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$).

  • 0
    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).2012-07-12
1

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$.

  • 0
    @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.2012-07-12
1

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$.

1

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}. $