0
$\begingroup$

I am trying to solve this below problem from Hammack's Book of Proof.

Here $F_n$ is the $n$th Fibonacci number. Prove that $$ F_n = \frac{\left(\frac{1 + \sqrt{5}}{2} \right)^n - \left(\frac{1 - \sqrt{5}}{2} \right)^n}{\sqrt{5}}. $$

The formula for the Fibonacci numbers I have is: $F_1 = 1$, $F_2 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 3$. My first point of confusion is exactly how many base cases I have access to. I want to prove the $n+1$ case after having proved the $n$ case, but I really want both $n$ and $n+1$ to have this recursive formula, which suggests to me that I need to prove, manually, the $n=1$, $n=2$, and $n=3$ cases. From there, it's just a matter of assuming it for $n$ and brute-forcing the $n+1$ case.

Is that correct? This is really my only point of confusion. I can work out the computation.

$\endgroup$
6
  • 2
    $\begingroup$ You can check for $n=1$ and $n=2$ and then prove that the formula is still valid for $F_{n+2}$ knowing that $F_{n+1}$ and $F_n$ are given by your formula. $\endgroup$
    – Atmos
    Sep 7, 2021 at 19:13
  • $\begingroup$ Ok, so proving $n=1$ and $n=2$ allows me to assume the result for $n \geq 2$ and then use the recursive formula for $F_{n+1}$ because $n+1 \geq 3$. Is that the idea? $\endgroup$
    – Brad G.
    Sep 7, 2021 at 19:15
  • 1
    $\begingroup$ "Ok, so proving 𝑛=1 and 𝑛=2 allows me to assume the result for 𝑛≥2" Not at all. It allows you show that the result for one value of n ≥ 2 implies the result for n+1. That would suffice to prove the general statement by induction. $\endgroup$
    – Dan Asimov
    Sep 7, 2021 at 19:20
  • 2
    $\begingroup$ You will prove that $F_{n+2}=\frac{\left(\frac{1 + \sqrt{5}}{2} \right)^{n+2} - \left(\frac{1 - \sqrt{5}}{2} \right)^{n+2}}{\sqrt{5}}$ knowing that $F_{n+1}=\frac{\left(\frac{1 + \sqrt{5}}{2} \right)^{n+1} - \left(\frac{1 - \sqrt{5}}{2} \right)^{n+1}}{\sqrt{5}}$ and $F_{n}=\frac{\left(\frac{1 + \sqrt{5}}{2} \right)^{n} - \left(\frac{1 - \sqrt{5}}{2} \right)^{n}}{\sqrt{5}}$ as you will use $F_{n+1}$ AND $F_n$ you need to initialize with $n=1$ AND $n=2$. $\endgroup$
    – Atmos
    Sep 7, 2021 at 19:22
  • 1
    $\begingroup$ consider $\phi^2=\phi+1$ $\endgroup$
    – John Joy
    Sep 7, 2021 at 19:31

1 Answer 1

Reset to default
0
$\begingroup$

$F_0 = 0, F_1 = 1, F_{n} = F_{n-1} + F_{n-2}$

$\frac{1 + \sqrt {5}}{2},\frac {1 - \sqrt {5}}{2}$ are roots of the polynomial $x^2 - x - 1 = 0$

Rearranging we get $x^2 = x + 1$

Claim: $(\frac {1+\sqrt 5}{2})^n = F_{n-1} + F_{n}(\frac {1+\sqrt 5}{2})$

Proof by induction:

Base case n = 1
$(\frac {1+\sqrt 5}{2})^1 = 0 + F_1(\frac {1+\sqrt 5}{2})$

Suppose $(\frac {1+\sqrt 5}{2})^n = F_{n-1} + F_{n}(\frac {1+\sqrt 5}{2})$

We must show that $(\frac {1+\sqrt 5}{2})^{n+1} = F_{n} + F_{n+1} (\frac {1+\sqrt 5}{2})$ basd on the hypothesis.

$(\frac {1+\sqrt 5}{2})^{n+1}\\ (\frac {1+\sqrt 5}{2})^{n}(\frac {1+\sqrt 5}{2})\\ (F_{n-1} + F_n(\frac {1+\sqrt 5}{2}))(\frac {1+\sqrt 5}{2})\\ F_{n-1}(\frac {1+\sqrt 5}{2}) + F_n(\frac {1+\sqrt 5}{2})^2\\ F_{n-1}(\frac {1+\sqrt 5}{2}) + F_n(1 + \frac {1+\sqrt 5}{2})\\ F_n + (F_{n-1} + F_n)(\frac {1+\sqrt 5}{2})\\ F_n + F_{n+1}(\frac {1+\sqrt 5}{2})$

Do the same for $(\frac {1-\sqrt 5}{2})^n = F_{n-1} + F_n(\frac {1-\sqrt 5}{2}).$

Then
$\frac {(\frac {1+\sqrt 5}{2})^n - (\frac {1-\sqrt 5}{2})^n}{(\frac {1+\sqrt 5}{2}) - (\frac {1-\sqrt 5}{2})}\\ \frac {(F_{n-1} + F_n(\frac {1+\sqrt 5}{2})) - (F_{n-1} + F_n(\frac {1-\sqrt 5}{2}))}{(\frac {1+\sqrt 5}{2}) - (\frac {1-\sqrt 5}{2})}\\ \frac {F_n(\frac {1+\sqrt 5}{2}) - F_n(\frac {1-\sqrt 5}{2})}{(\frac {1+\sqrt 5}{2}) - (\frac {1-\sqrt 5}{2})}\\ F_n$

$\endgroup$

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