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