Skip to main content
corrected spelling
Source Link
Michael Lugo
  • 14k
  • 7
  • 58
  • 80

Putting $x_n = 1+y_n$, we have $y_{n+1} = y_n + \frac{y_n^2}{2}$. There is a standard method for analyzing recursions of the form $y_{n+1} = y_n+O(y_n^2)$. A good introduction is chapter 8.4 in de Bruijn's AsymptopicAsymptotic Methods in Analysis.

I'll do the first terms of the expansion for you. Set $z_n = 1/y_n$. Then $$z_{n+1} = \frac{1}{z_n^{-1}+z_n^{-2}/2} = z_n - 1/2 + O(1/z_n). \quad (\ast)$$ Since $x_n \to 1^{-}$, we have $y_n \to 0^{-}$ and $z_n \to - \infty$. Thus, for any $\epsilon>0$, we have $|z_{n+1} - (z_n-1/2)| < \epsilon$ for $n$ large enough and we deduce $z_n = - n/2 (1+o(1))$. Reversing our substitutions, $x_n = 1-2(1+o(1))/n$.

We can then deduce tighter bounds by "bootstrapping", plugging our previous bounds in $(\ast)$ to give $$z_{n+1} = z_n - 1/2 + O(1/n)$$ and thus $$z_{n} = -n/2+O(\log n).$$ Taking more terms in the Taylor series $(\ast)$, and bootstrapping repeatedly, we can get an asymtopic series in powers of $n^{-1}$ and $\log n$.

Putting $x_n = 1+y_n$, we have $y_{n+1} = y_n + \frac{y_n^2}{2}$. There is a standard method for analyzing recursions of the form $y_{n+1} = y_n+O(y_n^2)$. A good introduction is chapter 8.4 in de Bruijn's Asymptopic Methods in Analysis.

I'll do the first terms of the expansion for you. Set $z_n = 1/y_n$. Then $$z_{n+1} = \frac{1}{z_n^{-1}+z_n^{-2}/2} = z_n - 1/2 + O(1/z_n). \quad (\ast)$$ Since $x_n \to 1^{-}$, we have $y_n \to 0^{-}$ and $z_n \to - \infty$. Thus, for any $\epsilon>0$, we have $|z_{n+1} - (z_n-1/2)| < \epsilon$ for $n$ large enough and we deduce $z_n = - n/2 (1+o(1))$. Reversing our substitutions, $x_n = 1-2(1+o(1))/n$.

We can then deduce tighter bounds by "bootstrapping", plugging our previous bounds in $(\ast)$ to give $$z_{n+1} = z_n - 1/2 + O(1/n)$$ and thus $$z_{n} = -n/2+O(\log n).$$ Taking more terms in the Taylor series $(\ast)$, and bootstrapping repeatedly, we can get an asymtopic series in powers of $n^{-1}$ and $\log n$.

Putting $x_n = 1+y_n$, we have $y_{n+1} = y_n + \frac{y_n^2}{2}$. There is a standard method for analyzing recursions of the form $y_{n+1} = y_n+O(y_n^2)$. A good introduction is chapter 8.4 in de Bruijn's Asymptotic Methods in Analysis.

I'll do the first terms of the expansion for you. Set $z_n = 1/y_n$. Then $$z_{n+1} = \frac{1}{z_n^{-1}+z_n^{-2}/2} = z_n - 1/2 + O(1/z_n). \quad (\ast)$$ Since $x_n \to 1^{-}$, we have $y_n \to 0^{-}$ and $z_n \to - \infty$. Thus, for any $\epsilon>0$, we have $|z_{n+1} - (z_n-1/2)| < \epsilon$ for $n$ large enough and we deduce $z_n = - n/2 (1+o(1))$. Reversing our substitutions, $x_n = 1-2(1+o(1))/n$.

We can then deduce tighter bounds by "bootstrapping", plugging our previous bounds in $(\ast)$ to give $$z_{n+1} = z_n - 1/2 + O(1/n)$$ and thus $$z_{n} = -n/2+O(\log n).$$ Taking more terms in the Taylor series $(\ast)$, and bootstrapping repeatedly, we can get an asymtopic series in powers of $n^{-1}$ and $\log n$.

Source Link
David E Speyer
  • 156.3k
  • 14
  • 421
  • 763

Putting $x_n = 1+y_n$, we have $y_{n+1} = y_n + \frac{y_n^2}{2}$. There is a standard method for analyzing recursions of the form $y_{n+1} = y_n+O(y_n^2)$. A good introduction is chapter 8.4 in de Bruijn's Asymptopic Methods in Analysis.

I'll do the first terms of the expansion for you. Set $z_n = 1/y_n$. Then $$z_{n+1} = \frac{1}{z_n^{-1}+z_n^{-2}/2} = z_n - 1/2 + O(1/z_n). \quad (\ast)$$ Since $x_n \to 1^{-}$, we have $y_n \to 0^{-}$ and $z_n \to - \infty$. Thus, for any $\epsilon>0$, we have $|z_{n+1} - (z_n-1/2)| < \epsilon$ for $n$ large enough and we deduce $z_n = - n/2 (1+o(1))$. Reversing our substitutions, $x_n = 1-2(1+o(1))/n$.

We can then deduce tighter bounds by "bootstrapping", plugging our previous bounds in $(\ast)$ to give $$z_{n+1} = z_n - 1/2 + O(1/n)$$ and thus $$z_{n} = -n/2+O(\log n).$$ Taking more terms in the Taylor series $(\ast)$, and bootstrapping repeatedly, we can get an asymtopic series in powers of $n^{-1}$ and $\log n$.