0
$\begingroup$

Fibonacci numbers are defined as follows.

$$F_{1}= F_{2} = 1$$ When $n \geq 3$, $$F_{n} = F_{n-1} + F_{n-2}$$

Task: Prove the following statement using mathematical induction:

  • When $n \geq 2$, $$F_{n-1}F_{n+1} = F_{n}^2 + (-1)^n$$

The Base Case:

enter image description here


The Inductive Step:

enter image description here


I'm really confused about the inductive step. The answer makes absolutely no sense to me.

Questions:

  1. For the inductive step, why is the yellow area equal to the green area?
  2. For the inductive step, how do we arrive at the purple and red statement?

I think the answer given to me is too simplified and doesn't demonstrate a clear logical reasoning.

$\endgroup$
1
  • $\begingroup$ My apologies for anyone who is color blind. It's just easier for me to color code the statements. $\endgroup$ Dec 9, 2018 at 22:18

2 Answers 2

1
$\begingroup$
  1. The green part is $$f^2(k)+f(k)f(k+1)=(f(k-1)+f(k))f(k+1)-(-1)^k=f^2(k+1)+(-1)^{k+1},$$ i.e. the yellow part. Note that it's not supposed to be obvious at this stage that green = yellow; that they are is what the subsequent lines show. The important part is that red = yellow; that's why the inductive step works. The way the proof of this actually starts is by rewriting $f(k+2)$ as a sum to get the green expression.

  2. The purple part is equal to the line above it, by summing the coefficients of $f(k+1)$ and taking care with powers of $-1$. The red part rewrites the summed coefficient from the recursion relation, and then notes a square is present.

$\endgroup$
0
$\begingroup$
  1. Because, by definition, $f(k+2)=f(k+1)+f(k)$.
  2. First of all, $-(-1)^k=(-1)\times(-1)^k=(-1)^{k+1}$. Then,$$f(k)f(k+1)+f(k-1)f(k+1)=\bigl(f(k)+f(k-1)\bigr)f(k+1).$$So,$$f(k)f(k+1)+f(k-1)f(k+1)-(-1)^k=\bigl(f(k)+f(k-1)\bigr)f(k+1)+(-1)^{k+1}.\tag1$$But, by definition, $f(k+1)=f(k)+f(k-1)$. So, $(1)$ becomes$$f(k)f(k+1)+f(k-1)f(k+1)-(-1)^k=\bigl(f(k+1)\bigr)^2+(-1)^{k+1}.$$
$\endgroup$
2
  • $\begingroup$ 1. asked about the green expression, not the blue one. $\endgroup$
    – J.G.
    Dec 9, 2018 at 22:25
  • $\begingroup$ I've edited my answer. I hope that everything is clear now. $\endgroup$ Dec 9, 2018 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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