Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
What have you tried? Where are you stuck? –  JavaMan Nov 28 '12 at 5:41
    
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

2 Answers 2

up vote 1 down vote accepted

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}$

share|improve this answer
    
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}}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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