Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
2  
The "silver ratio" is not the negative of the reciprocal of the golden ratio... –  J. M. Jul 12 '12 at 9:32
    
en.wikipedia.org/wiki/Lucas_number –  PAD Jul 12 '12 at 9:39

4 Answers 4

up vote 2 down vote accepted

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

share|improve this answer
    
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$.

share|improve this answer
1  
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
1  
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. –  J. M. 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}. $$

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.