2

Prove by induction that the $i$th Fibonacci number satisfies the equality: $$F_i = \frac {\phi^i - \hat\phi{}^i}{\sqrt5}$$ where $\phi$ is the golden ratio and $\hat\phi$ is its conjugate.

Thanks for the help. This is the first time I have dealt with the Fibonacci sequence and the first time I have used induction, so please be really explicit in your answers.

egreg
  • 238,574
sdf
  • 29
  • 2
    How would you start to solve this problem? – Norbert May 05 '13 at 20:08
  • 1
    Start writing down how the Fibonacci sequence is defined. From there, what are your starting point(s)? What do you need to prove for the induction step? – vonbrand May 05 '13 at 20:10
  • http://math.stackexchange.com/questions/94989/prove-by-induction-fibonacci-equality?rq=1 – Amzoti May 05 '13 at 20:12
  • @Norbert I started by proving the base case for $F_0$ and $F_1$. I then tried to prove that $\phi^i - \hat\phi^i = \phi^{i-1} - \hat\phi^{i-1} + \phi^{i-2} - \hat\phi^{i-2}$ – sdf May 05 '13 at 20:12
  • 1
    Then I suggest you to multiply this equation by $\hat{\phi}^i$ – Norbert May 05 '13 at 20:14

2 Answers2

1

Since the $F_n$ are (uniquely) defined by $$F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}\text{ if }n\ge2,$$ you have to show that $f(n):=\frac{\phi^n-\hat\phi^n}{\sqrt 5}$ also fulfills $$f(0)=0,\qquad f(1)=1,\qquad f(n)=f(n-1)+f(n-2)\text{ if }n\ge2.$$

Thus you verify $F_0=f(0)$ and $F_1=f(1)$ directly and for $n\ge 2$ you conclude (from the assumption that $F_k=f(k)$ for $0\le k<n$) that also $f(n)=f(n-1)+f(n-2)=F_{n-1}+F_{n-2}=F_n$.

Hagen von Eitzen
  • 374,180
  • 1
    (-1) You even didn't checked where the guy stucked and hurried to write a solution – Norbert May 05 '13 at 20:16
  • @Norbert - there is so much going on here, and so much rich insight to be gained, that even if the original question is based on a bog-standard introduction to induction - if the person who posted this gets a sense of the mathematical connections from HvE's post, it was worth his giving this answer. – Mark Bennet May 05 '13 at 20:44
0

Let $P(i)$ be the proposition $$\text{The $i$th Fibonacci number is: } F_i = \frac{\phi^i - \hat{\phi}^i}{\sqrt{5}}.$$ To use induction, we must check that it is true for $i=1$. Then, assume that $P(i)$ is true. One must show that $P(i+1)$ is true by using this assumption.

The $i$th Fibonacci number has a definition via a recurrence relation: $$ F_{i+1} = F_i + F_{i-1},$$ with $F_0 = F_1 = 1$. This definition is the key to solving the last step in the above induction proof. Note that $\phi = (\sqrt{5}+1)/2$ and $\hat{\phi} = (\sqrt{5}-1)/2 = \phi-1$.

These clues hopefully put you on the right track.

Jas Ter
  • 1,539