# Induction problem? (ratio of consecutive Fibonacci numbers)

Define $a_1 = 1$ and for all natural $n$'s, $a_{n+1} = 1 + \dfrac{1}{a_n}$.
Prove that for every natural $n$, $$a_n = \dfrac{F_{n+1}}{F_n}.$$

I'm not sure if this is an induction problem or not, but could someone help me understand what is going on?

-
Compute the first few, by hand, expressing the answers in the form $\frac{x_n}{y_n}$. Soon you will see what's going on. – André Nicolas Nov 28 '12 at 5:43
Ok I'll try something and then I'll come back. – blutuu Nov 28 '12 at 5:46
Ok I've computed a few n terms and everything after n = 1 seems to produce fractions (that is if my arithmetic is correct). What would you think I should do? – blutuu Nov 28 '12 at 5:57
Yeah I hadn't thought about doing that until recently. I'll fix that – blutuu Nov 28 '12 at 6:23

It is very easy to show that at n = 1 it is true. Now we show the inductive step (assume it holds for $n$ and show it holds for $n+1$)

First we know that

$F_{n+2} = F_{n+1} + F_{n}$

and dividing by $F_{n+1}$ to both sides

$F_{n+2}/F_{n+1} = 1 + F_n/F_{n+1}$

Suppose $a_n = F_{n+1}/F_{n}$

Then by definition of $a_{n+1}$

$\displaystyle a_{n+1} = 1+ \frac{1}{a_{n}}$ $\displaystyle = 1+\frac{1}{\frac{F_{n+1}}{F_{n}}}$ $\displaystyle =1 + \frac{F_n}{F_{n+1}}$

Therefore $a_{n+1} = F_{n+2} /F_{n+1}$

-
I'm confused on the step where you set Fn+2 = Fn+1 + Fn. How did you get there from the previous step? – blutuu Nov 28 '12 at 7:05
It is independent of the previous step. It is just the definition of the Fibonacci Sequence. I shall edit now for it to be more clear. – Keith Reyes Nov 28 '12 at 7:47
Okay then. Thanks – blutuu Nov 28 '12 at 7:54

Yes, induction is the natural choice here.

Base Step: $a_1 = 1/1 = F_2 / F_1$

Inductive Step: Suppose $a_n = F_{n+1}/F_n$ for an arbitrary $n \in \mathbb{N}$. Then $$a_{n+1} = 1 + \frac{1}{a_n} = 1 + \frac{F_n}{F_{n+1}} = \frac{F_{n+1}}{F_{n+1}} + \frac{F_n}{F_{n+1}} = \frac{F_{n+2}}{F_{n+1}}$$

-