Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So given this recurrence relation (not how it was presented, but equivalent and much nicer)

$$ x_{n+1} = \dfrac{x_n + nx_{n-1}}{n+1}; \ x_0 = 0,\ x_1 = 1 $$

I just can't find what the limit as $n$ goes to infinity is. It was straightforward to show it was convergent, and oscillatory about its limit, and I know the limit is going to be between $0.6$ and $0.75$ (through repeated calculation). The next step of finding the exact limit, though, I'm completely lost on.

share|improve this question
1  
An approach is to compute the series $X(t)=\sum\limits_nx_nt^n$ and to deduce $\lim\limits_{n\to\infty}x_n=\lim\limits_{t\to1}(1-t)X(t)$ (which should equal $\ln(2)$, unless I am mistaken). –  Did Aug 7 '13 at 14:36
    
I can say that the limit is somewhere in $(0.613606,0.613806)$ after 10000 iterations. –  TZakrevskiy Aug 7 '13 at 14:36
    
The Maple commands $$sol := rsolve({(n+1)*S(n+1) = S(n)+n*S(n-1), S(0) = 0, S(1) = 1}, S(n)) $$ and $$limit(sol, n = infinity) $$ produce $$\ln \left( 2 \right) -1/2\, \left( -1 \right) ^{n} \left( \Psi \left( 1/2\,n+1 \right) -\Psi \left( 1/2\,n+1/2 \right) \right) $$ and $\ln 2$. –  user64494 Aug 7 '13 at 15:35
    
hi Anyone here can give some input on: [What is the Probability that a Knight stays on chessboard after N hops][1] [1]: math.stackexchange.com/questions/464049/… –  Arnab Dutta Aug 10 '13 at 10:46

2 Answers 2

up vote 4 down vote accepted

If $$S_n = \sum_{j=1}^{n} \frac{(-1)^{j+1}}{j}$$

then we can prove that

$$(n+1)S_{n+1} = S_n + nS_{n-1}$$

Since $x_1 = S_1$ and $x_2 = S_2$ we have that $x_n = S_n$ for $n \ge 1$

Thus $\lim x_n = \lim S_n = \log 2$

share|improve this answer

Define ${\rm F}\left(z\right) \equiv \sum_{n = 0}^{\infty}z^{n}\,x_{n}\ \ni\ {\rm F}\left(0\right) = 0$ and ${\rm F}\,'\left(1\right) = 1$. Then

\begin{eqnarray*} 0 & = & \sum_{n = 1}^{\infty}z^{n}\left\lbrack% \left(n + 1\right)x_{n + 1} - x_{n} - nx_{n - 1} \right\rbrack \\ & = & \sum_{n = 2}^{\infty}z^{n - 1}\,n\,x_{n} - \sum_{n = 1}^{\infty}z^{n}\,x_{n} - \sum_{n = 0}^{\infty}z^{n + 1}\left(n + 1\right)x_{n} \\ & = & \left\lbrack{\rm F}\,'\left(z\right) - 1\right\rbrack - {\rm F}\left(z\right) - \left\lbrack z^{2}{\rm F}\,'\left(z\right) + z{\rm F}\left(z\right)\right\rbrack \\ & = & \left(1 - z^{2}\right){\rm F}\,'\left(z\right) - \left(1 + z\right){\rm F}\left(z\right) - 1 \end{eqnarray*}

$$ \left(z - 1\right){\rm F}\,'\left(z\right) + {\rm F}\left(z\right) = -\,{1 \over z + 1} \quad\Longrightarrow\quad {{\rm d}\left\lbrack\left(z - 1\right){\rm F}\left(z\right)\right\rbrack \over {\rm d}z} = -\,{1 \over z + 1} $$

$$ \left(z - 1\right){\rm F}\left(z\right) = -\int_{0}^{z}{{\rm d}z \over z + 1} = -\ln\left(1 + z\right) $$

$$ \quad\Longrightarrow\quad {\rm F}\left(z\right) = {\ln\left(1 + z\right) \over 1 - z} = z+z^2/2+(5 z^3)/6+(7 z^4)/12+(47 z^5)/60+O(z^6) $$

$$ x_{0} = 0,\ x_{1} = 1,\ x_{2} = {1 \over 2},\ x_{3} = {5 \over 6}\,\ x_{4} = {7 \over 12}\,\ x_{5} = {47 \over 60}\,\quad\mbox{etc...} $$

In general \begin{align} {\rm F}\left(z\right) &= {\ln\left(1 + z\right) \over 1 - z} = \sum_{s = 0}^{\infty}z^{s}\sum_{k = 0}^{\infty}{\left(-1\right)^{k} \over k + 1}\,z^{k + 1} \sum_{n = 1}^{\infty}\delta_{n, s + k + 1} = \sum_{n = 1}^{\infty}z^{n} \sum_{s = 0}^{\infty}\sum_{k = 0}^{\infty}{\left(-1\right)^{k} \over k + 1}\, \delta_{k,n - s -1} \\[3mm]&= \sum_{n = 1}^{\infty}z^{n} \sum_{s = 0}^{n - 1}{\left(-1\right)^{n - s -1} \over \left(n - s -1\right) + 1} = \sum_{n = 1}^{\infty}z^{n} \sum_{s = 0}^{n - 1}{\left(-1\right)^{s} \over s + 1} \end{align}

$$ \quad\Longrightarrow\quad x_{n} = \sum_{s = 0}^{n - 1}{\left(-1\right)^{s} \over s + 1}\,, \qquad n \geq 1 $$

$$ \lim_{n \to \infty}x_{n} = \sum_{s = 0}^{\infty}{\left(-1\right)^{s} \over s + 1} = \sum_{s = 0}^{\infty}{\left(-1\right)^{s} \over s + 1}\ 1^{s + 1} = \ln\left(1 + 1\right) = {\Large \ln\left(2\right)} $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.