How can I solve a difference equation where one of the variables is inverted?

Question

I'm asked to solve $z_{t+1}= 1 + \frac 1{z_t} $ and I have no clue where to start.

$ 1+ \frac 1{z_t} $ looks similar to $ \Delta log t $ which is $ log({1+ \frac 1{t}}) $ but I'm not sure what to do with that, if it's even related.

Answer 1

This is not a proof but just observation.

Suppose that $z_0=a \neq 0$ and compute the first values $$z_1=\frac{a+1}a \qquad z_2=\frac{2a+1}{a+1}\qquad z_3=\frac{3 a+2}{2 a+1}\qquad z_4=\frac{5 a+3}{3 a+2}\qquad z_5=\frac{8 a+5}{5 a+3}$$ $$z_6=\frac{13 a+8}{8 a+5}\qquad z_7=\frac{21 a+13}{13 a+8}\qquad z_8=\frac{34 a+21}{21 a+13}\qquad z_9=\frac{55 a+34}{34 a+21}\qquad z_{10}=\frac{89 a+55}{55 a+34}$$ Have a look at the coefficients which appear everywhere; they are $[1,2,3,5,8,13,21,34,55,89,\cdots]$ and they really look like Fibonacci numbers . So, what it seems is that $$z_n=\frac {a F_{n+1}+F_n}{a F_n+F_{n-1} }$$

Answer 2

Just compute the first few terms in the sequence (in terms of $z_0$), and you should see a pattern, which you can then prove by induction.