1
$\begingroup$

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?

  • 0
    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.2012-11-28
  • 0
    Ok I'll try something and then I'll come back.2012-11-28
  • 0
    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?2012-11-28
  • 0
    Yeah I hadn't thought about doing that until recently. I'll fix that2012-11-28

2 Answers 2

1

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

  • 0
    I'm confused on the step where you set Fn+2 = Fn+1 + Fn. How did you get there from the previous step?2012-11-28
  • 0
    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.2012-11-28
  • 0
    Okay then. Thanks2012-11-28
1

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