Recurrences pop up a lot. I quite like them for the following reason: - Fairly often you can plot them and guess an approximate / asymptotitc closed form - Then you can prove this hopefully

Sometimes you can hit them with generating functions. But whatever.

Here’s one:

\[x_{n+1}= x_n + \frac{1}{x_n}.\] Now, this is not afaik ameneble to gfs. But on the other hand, if we remember calculus, we might realize that this has a striking similarity to the linear approximations to the function \(\sqrt{2x}\). In fact, if you plot this function it basically is just \(\sqrt{2x}\), if you seed with an initial condition of \(x_1=2\) or something. Cool.