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

We have $a_{n+1}-a_n= 1/2 + 1/(2*(2a_n+\sqrt{4a_n^2+1}))$.

That’s around $1/2+1/8a_n$. $a_n$ is around $n/2$, so that’s $1/2+1/4n$. That integrates to $n/2+1/4 \log n$, so your additional term is not a constant.

Answer 2

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)$.

Answer 3

The question is about a sequence defined by $\,a_0 = 1\,$ and for $\,n\ge 0\,$ $$ a_{n+1} = \frac{1+\sqrt{4{a_n}^2+1}}2. \tag{1} $$

You asked

how do we get an explicit formula for $a_n$? Is there a simpler way to derive the approximation?

I doubt very much that there is a closed form expression for $\,a_n\,$ so that is not going to help. However, there is a simple way to approximate it. Define the function

$$ f(x) := \frac{1+\sqrt{4x^2+1}}2 = \frac12 + |x| \sqrt{1+\frac1{4x^2}}. \tag{2} $$

Use the approximation $\, \sqrt{1+x} \approx 1 + \frac{x}2,\,$ good for $\,0<x<\!\!<1\,$ and the recursion equation $(1)$ to get that

$$ a_{n+1} \approx \frac12 + a_n \left(1 + \frac1{8a_n^2}\right) = a_n + \frac12 + \frac1{8a_n}. \tag{3} \,$$

The first two terms of this approximation leads to $\, a_n \approx \frac12 n + c\,$ for some constant $\,c.\,$ Substitute this back into the approximation and use the known Harmonic series approximation to improve the approximation to $\, a_n \approx \frac12 n + \frac14\log(n) + c\,$ for some other constant $\,c.\,$ It is possible to do better, though.

---

Similar questions such as MSE question 2861768 suggest the following approach.

Define, for some constant $\,c_0\,$ yet to be determined, the variables $$x := 1/(n+c_0),\qquad y := \log(x). \tag{4} $$

Consider an Laurent series Ansatz $$ a_n = f(x) := c_1 x^{-1} + (c_2+c_3y) + (c_4+c_5y+c_6y^2)x^1 + \dots \tag{5} $$ where $\,c_1,c_2,\dots\,$ are more constants to be determined. Substitute equation $(5)$ in the recursion equation $(1)$ and solve for the constants. The result is $$ f(x) = \frac12 x^{-1} + (-y)\frac14 + (-y)\frac{x}8 + (1-6y-3y^2)\frac{x^2}{96} + \dots\,. \tag{6} $$ Substitute equation $(4)$ into equation $(6)$ with $\,c_0 \approx 1.6464707$ to get $$ a_n \approx b_n := \frac1{2x} - \frac{y}4 \left(1+\frac{x}2\right). \tag{7} $$

As a check, here is a small table of sequence values: $$\begin{array}{|c|c|c|} \hline n & a_n & b_n \\ \hline 1 & 1.6180340 & 1.6125102 \\ \hline 2 & 2.1935271 & 2.1910250 \\ \hline 3 & 2.7497913 & 2.7485869 \\ \hline 4 & 3.2948797 & 3.2943141 \\ \hline 5 & 3.8326014 & 3.8323789 \\ \hline \end{array}$$