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