Find a prove the formula for given sequence by induction

Question

Let $a_0 = 1$ and $$a_{n} = \frac{a_{n-1}}{2a_{n-1}+1}$$

how to find that formula of the sequence?

Answer 1

First we divide through by $a_{n-1}$, to rewrite the seqence as follows; $$a_{n}=\frac{a_{n-1}}{2a_{n-1}+1}=\frac{1}{2+\frac{1}{a_{n-1}}}$$

Writing out the first few terms gives;

So $\{a_{n}\}=\{1, \frac{1}{3}, \frac{1}{5}, \frac{1}{7},...\}$

This looks like the sequence of all odd fractions, $a_{n}=\frac{1}{2n+1}$ to me! Can you prove it by induction from here?

Answer 2

you may rewrite your difference equation as $$ \frac{1}{a_n}=2+\frac {1}{a_{n-1}} $$ Call $b_n=\frac{1}{a_n}$, then you get the arithmetic progression $$ b_n=b_{n-1}+2, $$ with $b_0=1$, $\implies b_n=2n+1\implies a_n=\frac{1}{2n+1}$.