Intereting Posts

Why can no prime number appear as the length of a hypotenuse in more than one Pythagorean triangle?
Why is a set of orthonormal vectors linearly independent?
Drawing a tetrahedron from a parellelepiped to convince myself it is 1/6th the volume,
Show that for this function the stated is true.
Show $\psi$ and $\Delta$ are identifiable
A question regarding the hitting time formula in brownian motion
Help on differential equation $y''-2\sin y'+3y=\cos x$
How prove this $f(a)\le f(b)$
This sigma to binom?
Every closed $C^1$ curve in $\mathbb R^3 \setminus \{ 0 \}$ is the boundary of some $C^1$ 2-surface $\Sigma \subset \mathbb R^3 \setminus \{ 0 \}$
Proving that the exponential function is continuous
Proof of Pythagorean theorem without using geometry for a high school student?
How many integers between have digit sum 20?
Are the rings $k]$ and $k]$ Gorenstein? (Matsumura, Exercise 18.8)
a general continued fraction satisfying $\frac{(i+\Theta\sqrt{z})^m}{(i-\Theta\sqrt{z})^m}=\frac{(ik+\sqrt{z})^{m+1}}{(ik-\sqrt{z})^{m+1}}$

let sequence $\{a_{n}\}$ such $$a_{1}=1,a_{n+1}=1+\dfrac{n}{a_{n}}$$

show that:

$$a_{n}=\sqrt{n}+\dfrac{1}{2}-\dfrac{1}{8\sqrt{n}}+o\left(\dfrac{1}{\sqrt{n}}\right)?$$

- Proof that $\frac{2}{3} < \log(2) < \frac{7}{10}$
- Is there a series to show $22\pi^4>2143\,$?
- What is the correct value of $\pi$
- Bounds on $ \sum\limits_{n=0}^{\infty }{\frac{a..\left( a+n-1 \right)}{\left( a+b \right)…\left( a+b+n-1 \right)}\frac{{{z}^{n}}}{n!}}$
- $n \approxeq k + 2^{2^k}(k+1)$. How can one get the value of $k(n)$ from this equation?
- When the approximation $\pi\simeq 3.14$ is NOT sufficent

- Heat equation, boundary gradient singularity
- Big O/little o true/false
- Euler numbers grow $2\left(\frac{2}{ \pi }\right)^{2 n+1}$-times slower than the factorial?
- Numerical Approximation of Differential Equations with Midpoint Method
- Maximum of Polynomials in the Unit Circle
- On finding polynomials that approximate a function and its derivative (extensions of Stone-Weierstrass?)
- Determining the Asymptotic Order of Growth of the Generalized Harmonic Function?
- How to prove that $\omega (n) = O\Big{(} \frac{\log(n)}{\log(\log(n))}\Big{)}$ as $n \to \infty$?
- Where am I violating the rules?
- The sum $\sum\limits_{n \ge 0} \binom{m-1}{n} \frac{n!}{m^n} + \binom{n+1}{2}\binom{m-1}{n-1}\frac{(n-1)!}{m^n}$ is asymptotic to $\sqrt{9πm/8}$

I will present two approaches to this question. The first is less advanced and easier but also yields a less optimal result.

Consider

the auxiliary sequence $b_n =\sqrt{n+\frac{1}{4}}+\frac{1}{2}$. This is

the unique positive solution to the $P_n(X)=0$ where $P_n(X)=X^2-X-n$.

${\bf Lemma~1.}$ For every $n\geq1$, we have

$b_{n+1}\geq 1+\dfrac{n}{b_{n-1}}$.

*Proof*. Indeed, let $u=1+\frac{n}{b_{n-1}}$ then

$$u^2-u=\frac{(n+b_{n-1})n}{b_{n-1}^2}=\frac{(n+b_{n-1})n}{b_{n-1}+n-1}=

n+\frac{n}{b_{n-1}+n-1}\leq n+1$$

since $b_{n-1}\geq 1$. This shows that $P_{n+1}(u)\leq0$ and

consequently $u\leq b_{n+1}$ as desired.$\qquad \square$

${\bf Lemma~2.}$ For every $n\geq1$, we have

$b_{n-1}\leq a_n \leq b_n$.

*Proof*. This is now an easy induction. Clearly true for $n=1$, and if

it is true for some $n$ then

$$

b_n=1+\frac{n}{b_n}\leq 1+\frac{n}{a_n}\leq 1+\frac{n}{b_{n-1}}\leq

b_{n+1}.

$$

and the result follows.$\qquad \square$

It follows that

$$

\sqrt{n-\frac{3}{4}}-\sqrt{n}\leq a_n-\sqrt{n}-\frac{1}{2}\leq \sqrt{n+\frac{1}{4}}-\sqrt{n}

$$

Thus

$$\sqrt{n}\left\vert a_n-\sqrt{n}-\frac{1}{2}\right\vert\leq \frac{3}{4(1+\sqrt{1-3/(4n)})}\leq \frac{1}{2}$$

So, we have proved that, for every $n\geq 1$ we have

$$

a_n= \sqrt{n}+\frac{1}{2}+{\cal O} \left(\frac{1}{\sqrt{n}}\right)

$$

This is not the desired expansion but it has the merit to be easy to prove.

The general reference in this part is the book of D. Knuth. “The art of Computer programming, Vol III, second edition, pp.63–65”.

Let $I(n)$ be the number of involutions in the symmetric group $S_n$, ($i.e.$ $\sigma\in S_n$ such that $\sigma^2=I$). It is well-known that $I(n)$ can be calculated inductively by

$$

I(0)=I(1)=1,\qquad I(n+1)=I(n)+nI(n-1)

$$

This shows that our sequence $\{a_n\}$ is related to these numbers by the formula

$$a_n=\frac{I(n+1)}{I(n)}.$$

So, we can use what we know about these numbers, In particular, the following asymptotic expansion, from Knuth’s book:

$$

I(n+1)=\frac{1}{\sqrt{2}} n^{n/2}e^{-n/2+\sqrt{n}-1/4}\left(1+\frac{7}{24\sqrt{n}}+{\cal O}\left(\frac{1}{n^{3/4}}\right)\right).

$$

Now, it is a “simple” matter to conclude from this that $a_n$ has the desired asymptotic expansion.

**Edit:** In fact the term $\mathcal{O}(n^{-3/4})$ effectively destroys the asymptotic expansion as mercio noted, But in fact we have

$$

I(n+1)=\frac{1}{\sqrt{2}} n^{n/2}e^{-n/2+\sqrt{n}-1/4}\left(1+\frac{7}{24\sqrt{n}}+{\cal O}\left(\frac{1}{n}\right)\right).

$$

This is shown by WIMP AND ZEILBERGER in their paper “Resurrecting the Asymptotics

of Linear Recurrences”, that can be found here.

It will be simpler in what follows to use two steps at once, so we can start by computing the relationship $a_{n+2} = \frac{a_n(n+2) + n}{a_n + n}$, and letting $b_n = a_n / \sqrt n$ we get $b_{n+2} = \frac {b_n (1 + 2/n) + 1/\sqrt n}{b_n\sqrt{1/n+2/n^2} + \sqrt{1+2/n}}$.

Let’s denote $\begin{bmatrix} a & b \\ c & d \end{bmatrix} x = \frac {ax+b}{cx+d}$.

If we have a relation $b_{n+2} = \begin{bmatrix} 1+A & B \\ C & 1+D \end{bmatrix} b_n$ where each $A,B,C,D$ is an $O(1/\sqrt n)$ and we look then at some $c_n = (b_n-k)\sqrt n$, we obtain on the sequence $c_n$ the same kind of relation (so with dominant term still begin $I_2$) with

$$A’ = (1+A-kC)\sqrt{1+2/n}-1, \\B’ = (B-kD+kA-k^2C)\sqrt{n+2}, \\

C’ = C/\sqrt n, \\ D’ = D+kC$$.

Right now, $C$ is still as big as everyone else, so to make $B’$ not an order of magnitude bigger than the rest, we have to solve a degree $2$ equation in $k$, which gives $k= \pm 1$.

If we define $c_n = (b_n-1)\sqrt n$, we get $A’ = -n^{-1/2} + O(n^{-1}), D’ = +n^{-1/2} + O(n^{-1}), C’ = O(n^{-1}), B’ = O(n^{-1/2})$.

From now $C’$ will continue to plummet, the dominant terms of $A’$ and $D’$ will not be able to change, and so to make the next $B$ into an $O(n^{-1/2})$ term, we will have to pick $k = $ the constant term of $B/(A-D)$.

What this tells us is that there are exactly two asymptotic developments for $a_n$ whose error terms at each level obey a recurrent relation of the form $r_{n+2} = [I_2 + O(n^{-1/2})] r_n$.

Since all of this can be done algebraically, those two power series are $\sqrt n$ times the two solutions in $\Bbb Q[[n^{-1/2}]]$ to the original equation on $a_n/\sqrt n$ (and you go from one to the other by switching the sign of $\sqrt n$).

Now we can look at $u_n = ((((a_n/\sqrt n – 1)\sqrt n – \frac 12)\sqrt n + \frac 18)\sqrt n + \frac 18)\sqrt n$.

It satisfies $u_{n+2} = \begin{bmatrix}1 – n^{-1/2} + O(n^{-1}) && \frac 7 {64}n^{-1} + O(n^{-3/2}) \\ O(n^{-5/2}) && 1 + n^{-1/2} + O(n^{-1}) \end{bmatrix} u_n$,

(and each constant in those $O$ can be effectively computed)

This means that if you have $u_n$ close enough to $0$, then $u_{n+2} = (1-2n^{-1/2})u_n + O(n^{-1})$. So it should mean that for each bound $\delta$ there is an $n_0$ such that $\forall n > n_0, |u_n < \delta | \implies |u_{n+2} < \delta|$.

If you effectively compute $n_0$ for, say, $\delta = 1$, this allows you to provably check that a sequence $u_n$ stays bounded by finding a term $u_n$ with $n$ large enough that is below the $\delta$. If the asymptotic development is valid, a finite computation will be able to prove it.

I would love to see a proof that the asymptotic development is valid for every starting value of $a_n$ (except the one value that will stay away infinitely from the asymptotic formula and will instead obey the other asymptotic development)

- Where are the values of the sine function coming from?
- Interesting combinatorial identities
- Journals that publish papers quickly
- Find a constant that minimizes $\int_0^1 |e^x – c| \ dx$
- How to prove that a simple graph having 11 or more vertices or its complement is not planar?
- How to explain brackets to young students
- How to show $f$ is continuous at $x$ IFF for any sequence ${x_n}$ in $X$ converging to $x$ the sequence $f(x_n)$ converges in $Y$ to $f(x)$
- Integrable function and measure space
- A Math function that draws water droplet shape?
- Proving that $\mathbb R^3$ cannot be made into a real division algebra (and that extending complex multiplication would not work)
- What does $\mathbb{R} \setminus S$ mean?
- Left/Right Eigenvectors
- Closed-form Expression of the Partition Function $p(n)$
- Bounding the integral $\int_{2}^{x} \frac{\mathrm dt}{\log^{n}{t}}$
- Accessible Intro to Random Matrix Theory (RMT)