0
$\begingroup$

I'm having difficulty with the following, problem 5.3.7 from Gilbert Strang's "Linear Algebra and its Application".

The numbers $\lambda_1^k$ and $\lambda_2^k$ satisfy the Fibonacci rule $F_{k+2}=F_{k+1} + F_k$ :

$\lambda_1^{k+2}=\lambda_1^{k+1} + \lambda_1^k$ and $\lambda_2^{k+2}=\lambda_2^{k+1} + \lambda_2^k$

Prove this by using the original equation for the $\lambda's$ (Multiply it by $\lambda^k$)

Then any combination of $\lambda_1^k$ and $\lambda_2^k$ satisfies the rule.

The combination $F_k=(\lambda_1^k-\lambda_2^k)/(\lambda_1-\lambda_2)$ gives the right start of $F_0=0$ and $F_1=1$.

I'm not sure what "the original equation for the $\lambda's$" is, or what I'm supposed to prove. Can someone please help?

  • 1
    What *is* "the original equation for the $\lambda'$s"? Where did you encounter this problem, and in what context? The more you can tell us about that, the more likely we'll be able to help you.2012-11-11
  • 0
    That is the part that also confuses me. It is a problem of the book "linear algebra and its application, 5.3.7", and I'm not sure what the 'original equation' means, also I can't find any 'equation for lambda' in previous pages...2012-11-11
  • 0
    Anyway, I can't understand what is the main point of this problem. What should I prove? The above two equations for lambdas? By using the Fibonacci formula?2012-11-11
  • 0
    Who would the book's author(s) be? Have you stated the *entire* problem?2012-11-11
  • 0
    The author is Gilbert Strang.2012-11-11

2 Answers 2

0

It looks to me like $\lambda_1$ and $\lambda_2$ were defined earlier, probably as eigenvalues of the matrix $\left( \begin {matrix} 1&1\\1&0 \end {matrix} \right)$ so $\lambda_1=\frac 12(1+\sqrt 5)$ and $\lambda_2=\frac 12(1-\sqrt 5)$. You are now supposed to prove the sentence just under "Fibonacci Rule".

  • 0
    The proof first takes the $\lambda s$ and converts these into two different solutions to the fibonacci equation. Then you will need to show that if you have these different solutions, any linear combination of them - i.e. $a\lambda_1^n+b\lambda_2^n$ will also fit the fibonacci rule. The third part of the proof is to find the combination which gives the correct first two values, solving for $a$ and $b$. Once this is done, you are done, because the first two values determine all the others by repeated application of the rule.2012-11-11
  • 0
    @Ross Millikan I know that it is late of an answer but right now I was also trying to solve the same exercise. So is it possible to verify the validity of my answer? Thanks.2017-02-20
0

For me there are three parts on this exercise.

Part A: Prove $\lambda_2^{k+2}=\lambda_2^{k+1} + \lambda_2^k$ and $\lambda_1^{k+2}=\lambda_1^{k+1} + \lambda_1^k$.

To do that we need

  1. $F_{k+2} = F_{k+1}+F_{k}$ and
  2. $F_{k+2} = c_1\lambda_1^k + c_2\lambda_2^k$

Replacing 2. in 1. we have:

$$c_1\lambda_1^{k+2} + c_2\lambda_2^{k+2} = c_1[\lambda_1^{k+1}+\lambda_1^{k}]+c_2[\lambda_2^{k+1}+\lambda_2^{k}]$$

Based on the last equation, we may say that $\lambda_2^{k+2}=\lambda_2^{k+1} + \lambda_2^k$ and $\lambda_1^{k+2}=\lambda_1^{k+1} + \lambda_1^k$ is true.

Part B: Prove that Fibonacci rule $F_{k+2} = c_1\lambda_1^k + c_2\lambda_2^k$ is true for any $c_1$ and $c_2$.

From Part A we may have:

$$c_1\underbrace{[\lambda_1^{k+2}-(\lambda_1^{k+1}+\lambda_1^{k})]}_{zero} = c_2\underbrace{[\lambda_2^{k+2}-(\lambda_2^{k+1}+\lambda_2^{k})]}_{zero}$$

The later equation is true for any $c_1$ and $c_2$.

Part C: The combination $F_k = (\lambda_1^k-\lambda_2^k)/(\lambda_1-\lambda_2)$ gives the right start of $F_0$ and $F_1$.

Easily, using the later combination for $n=0$ and $n=1$ we have the Fibonacci start $F_0=0$ and $F_1=1$.