0
$\begingroup$

I'm a bit unsure about going about a Fibonacci sequence proof using induction. the question asks:

The Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, ..., which is commonly described by $ F_1 = 1, F_2 = 1 \text { and } F_{n+1} = F_n + F_{n−1}, ∀ \space n ∈ \mathbb{N}, n ≥ 2.$

Prove by induction that the $n^{th}$ term in the sequence is $$ F_n = \frac {(1 + \sqrt 5)^n − (1 −\sqrt 5)^n} {2^n\sqrt5} $$

I believe that the best way to do this would be to Show true for the first step, assume true for all steps $ n ≤ k$ and then prove true for $n = k + 1.$

However I'm unsure how to go about this, I'd really appreciate any help or if anyone has a better way of proving this through induction.

$\endgroup$
  • $\begingroup$ Well you basically "just" need to show that $F_{n+2} - F_{n+1} - F_n = 0$ assuming that the formula for $F_{n+1}$ and $F_n$ is true. $\endgroup$ – Zubzub Mar 31 '17 at 13:30
  • $\begingroup$ math.stackexchange.com/questions/350165/… $\endgroup$ – Bram28 Mar 31 '17 at 16:27
0
$\begingroup$

First of all, we rewrite

$$F_n=\frac{\phi^n−(1−\phi)^n}{\sqrt5}$$

Now we see \begin{align} F_n&=F_{n-1}+F_{n-2}\\ &=\frac{\phi^{n-1}−(1−\phi)^{n-1}}{\sqrt5}+\frac{\phi^{n-2}−(1−\phi)^{n-2}}{\sqrt5}\\ &=\frac{\phi^{n-1}−(1−\phi)^{n-1}+\phi^{n-2}−(1−\phi)^{n-2}}{\sqrt5}\\ &=\frac{\phi^{n-2}(\phi+1)−(1−\phi)^{n-2}((1-\phi)+1)}{\sqrt5}\\ &=\frac{\phi^{n-2}(\phi^2)−(1−\phi)^{n-2}((1-\phi)^2)}{\sqrt5}\\ &=\frac{\phi^n−(1−\phi)^n}{\sqrt5}\\ \end{align}

Where we use $\phi^2=\phi+1$ and $(1-\phi)^2=2-\phi$. Now check the two base cases and we're done!

Turns out we don't need all the values below $n$ to prove it for $n$, but just $n-1$ and $n-2$ (this does mean that we need base case $n=0$ and $n=1$).

$\endgroup$

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.