Deriving an approximation for a recursive sequence

Question

Let $a_0=1$ and $a_{n+1}=\frac{1+\sqrt{4{a_n}^2+1}}{2}$ how can we show that for large $n: a_n \approx \frac{n}{2} + 2$ ?

For large $a$ the rate of change is constant so the approximation is of the form $a_n \approx m \cdot n +b$

$$\frac{\Delta a}{\Delta n} = \frac{a_{n+1}-a_n}{1} = \frac{1 + \sqrt{4{a_n}^2+1}}{2} – a_n \qquad m = \lim \limits_{a \to \infty} \frac{1 + \sqrt{4a^2+1}}{2} – a = \frac{1}{2}$$

In order to get $b$ we need to evaluate $\lim \limits_{n \to \infty} a_n – \frac{n}{2}$, how do we get an explicit formula for $a_n$? Is there a simpler way to derive the approximation?

Answer 1

Rearranging things a bit, we have \begin{align*}a_{n+1}-a_n&=\left(\sqrt{1+\frac1{4a_n}}+1-\frac1{2a_n}\right)^{\!-1}\\[.4em]&=\left(2-\frac3{8a_n}+o\!\left(\frac1{a_n}\right)\right)^{\!-1}\\[.4em]&=\frac12+\frac3{32a_n}+o\!\left(\frac1{a_n}\right)\!,\end{align*} where we used that $a_n^{-1}\to0$ (i.e., $a_n\to\infty$). This shows that:

1. $\displaystyle a_{n+1}-a_n\xrightarrow[n\to\infty]{}\frac12,\enspace$ hence $\displaystyle a_n\sim\frac n2;\\[1em]$
2. $\displaystyle a_n-\frac n2\sim\frac3{32}\sum_{k=1}^n\frac1{a_k}\sim\frac3{16}\sum_{k=1}^n\frac1k,\enspace$ so $\displaystyle a_n=\frac n2+\frac3{16}\,\log n+o(\log n)$.