Tag: Recurrence

Prove that the recursive sequence 1 / x_n+2 = 1 / x_n+1 + 1 / x_n converges

by RoRi

March 29, 2016

Prove that the sequence $\{ x_n \}$ be defined by the recursive relationship,

$x_0 = 1, \qquad x_1 = 1, \qquad \frac{1}{x_{n+2}} = \frac{1}{x_{n+1}} + \frac{1}{x_n}$

converges and find the limit of the sequence.

Proof. First, we show that the sequence $\{ x_n \}$ is monotonically decreasing for all $n \geq 1$ . For the base case we have $x_1 = 1$ and

$\frac{1}{x_2} = \frac{1}{1} + \frac{1}{1} = 2 \quad \implies \quad x_2 = \frac{1}{2}.$

Hence, $x_2 < x_1$ . Assume then that for all positive integers up to some $k$ we have $x_{k+1} < x_k$ . Then,

$\begin{align*} && \frac{1}{x_{k+2}} &= \frac{1}{x_{k+1}} + \frac{1}{x_k} \\[9pt] \implies && \frac{1}{x_{k+2}} &> \frac{1}{x_{k+1}} + \frac{1}{x_{k+1}} &(x_{k+1} < x_k \implies \frac{1}{x_{k+1}} > \frac{1}{x_k}) \\[9pt] \implies && \frac{1}{x_{k+2}} &> \frac{2}{x_{k+1}} \\[9pt] \implies && x_{k+2} &< \frac{x_{k+1}}{2} \\[9pt] \implies && x_{k+2} &< x_{k+1}. \end{align*}$

Thus, the sequences is monotonically decreasing. The sequence is certainly bounded below since all of the terms are greater than 0. Therefore, the sequence converges $. \qquad \blacksquare$

To compute the limit of the sequence, assume the sequence converges to a finite limit $L$ (justified since we just proved that it does indeed converge). Therefore,

$\begin{align*} && \lim_{n \to \infty} x_n &= L \\[9pt] \implies && \lim_{n \to \infty} \frac{1}{x_n} &= \frac{1}{L} \\[9pt] \implies && \lim_{n \to \infty} \left( \frac{1}{x_{n-1}} + \frac{1}{x_{n-2}} \right) &= \frac{1}{L} \\[9pt] \implies && \frac{1}{L} + \frac{1}{L} &= \frac{1}{L} \\[9pt] \implies && 2L &= L \\[9pt] \implies && L &= 0. \end{align*}$

Prove that the recursive sequence x_n+1 = (1+x_n)^1/2 converges

by RoRi

March 29, 2016

Prove that the sequence $\{ x_n \}$ whose terms are defined recursively by

$x_1 = 1, \qquad x_{n+1} = \sqrt{1+x_n}$

converges, and compute the limit of the sequence.

Proof. To show the sequence converges we show that it is monotonically increasing and bounded above. To see that it is monotonically increasing we use induction to prove that

$x_{n+1} > x_n \qquad \text{for all } n \in \mathbb{Z}_{>0}.$

For the case $n = 1$ we have

$x_{n+1} = x_2 = \sqrt{2}, \qquad \text{and} \qquad x_n = x_1 = 1.$

Since $\sqrt{2} >1$ , the statement holds in the case $n =1$ . Assume then that the statement holds for some positive integer $k$ . Then,

$\begin{align*} x_{k+2} - x_{k+1} &= \sqrt{1+x_{k+1}} - \sqrt{1+x_k}\\[9pt] &> 0 \end{align*}$

since $x_{k+1} > x_k$ by the induction hypothesis. Hence, $x_{k+2} > x_{k+1}$ so by induction $x_{n+1} > x_n$ for all positive integers $n$ . Hence, the sequence is monotonically increasing.
Next we use induction again to prove the sequence is bounded above by $2$ . For $n = 1$ we have $x_1 = 1 < 2$ so the hypothesis holds. Assume then that $x_k < 2$ for all positive integers up to $k$ . Then,

$\begin{align*} x_{k+1} &= \sqrt{1+x_k} \\ &\leq \sqrt{1+2} \\ &\leq 2. \end{align*}$

Hence, $x_n < 2$ for all positive integers $n$ .
This shows that the sequence converges $.\qquad \blacksquare$

To compute the limit, assume the sequence converges to a number $L$ (we just proved that it converges, so this assumption is valid). Then we have

$\begin{align*} \lim_{n \to \infty} x_{n+1} &= L & \implies && \lim_{n \to \infty} \sqrt{1+x_n} &= L \\[9pt] && \implies && \sqrt{1+L} &= L \\[9pt] && \implies && L^2 - L - 1 &= 0 \\[9pt] && \implies && L &= \frac{1 + \sqrt{5}}{2}. \end{align*}$

(We can discard the negative solution since to the quadratic at the end since the sequence is certainly all positive terms.)

Prove a formula for the integral from 0 to x of t^m(1+t)ⁿ

by RoRi

October 31, 2015

Define a function

$F(m,n) = \int_0^x t^m (1+t)^n \, dt \qquad m > 0, \quad n > 0.$

Prove that the following relation holds,

$(m+1)F(m,n) + nF(m+1,n-1) = x^{m+1}(1+x)^n.$

Using this find the value of $F(10,2)$ .

First, we evaluate $F(m,n)$ by parts, letting

$\begin{align*} u &= (1+t)^n & du &= n (1+t)^{n-1} \\[9pt] dv &= t^m \, dt & v &= \frac{1}{m+1} t^{m+1}. \end{align*}$

This gives us

$\begin{align*} F(m,n) &= \int_0^x t^m (1+t)^n \, dt \\[9pt] &= \left( uv - \int v \, du \right) \Bigr \rvert_0^x \\[9pt] &= \frac{t^{m+1}}{m+1}(1+t)^n \Bigr \rvert_0^x - \frac{n}{m+1} \int_0^x t^{m+1}(1+t)^{n-1} \, dt \\[9pt] &= \frac{x^{m+1}}{m+1} (1+x)^n - \frac{n}{m+1} F(m+1,n-1). \end{align*}$

Multiplying both sides by $m+1$ we have

$\begin{align*} (m+1) F(m,n) &= x^{m+1}(1+x)^n - nF(m+1,n-1) \\[9pt] \implies (m+1)F(m,n) + nF(m+1,n-1) &= x^{m+1}(1+x)^n. \qquad \blacksquare \end{align*}$

Then, to compute $F(10,2)$ we first compute $F(11,1)$ to use in our recurrence,

$\begin{align*} F(11,1) = \int_0^x t^{11} (1+t) \, dt &= \int_0^x (t^{11} + t^{12} ) \, dt \\[9pt] &= \frac{x^{12}}{12} + \frac{x^{13}}{13}. \end{align*}$

Then, applying the recurrence,

$\begin{align*} &&11 \cdot F(10,2) + 2 \cdot F(11,1) &= x^{11} (1+x)^2 \\[9pt] \implies && 11 \cdot F(10,2) + 2 \left( \frac{x^{12}}{12} + \frac{x^{13}}{13} \right) &= x^{13} + 2x^{12} + x^{11} \\[9pt] \implies && 11 \cdot F(10,2) &= \frac{11\cdot x^{13}}{13} + \frac{11 \cdot x^{12}}{6} + x^{11} \\[9pt] \implies && F(10,2) &= \frac{x^{13}}{13} + \frac{x^{12}}{6} + \frac{x^{11}}{11}. \end{align*}$

Establish a recurrence relation for a given integral

by RoRi

October 31, 2015

Define

$I_n = \int_0^1 (1-x^2)^n \, dx.$

Prove that this integral satisfies the recurrence relation,

$(2n+1)I_n = 2n I_{n-1}.$

Using this compute $I_2, I_3, I_4$ , and $I_5$ .

Proof. We start by integrating $I_n$ by parts with

$\begin{align*} u &= (1-x^2)^n & du &= -2xn(1-x^2)^{n-1} \, dx \\ dv &= dx & v &= x. \end{align*}$

Therefore we have

$\begin{align*} I_n = \int_0^1 (1-x^2)^n \, dx &= \left( uv - \int v \, du \right) \Bigr \rvert_0^1 \\[9pt] &= x(1-x^2)^n \Bigr \rvert_0^1 + 2n \int_0^1 x^2 (1-x^2)^{n-1} \, dx \\[9pt] &= 2n \int_0^1 x^2 (1-x^2)^{n-1} \, dx \\[9pt] &= 2n \int_0^1 (1-1+x^2)(1-x^2)^{n-1} \, dx \\[9pt] &= 2n \int_0^1 (1-x^2)^{n-1} \, dx - 2n \int_0^1 (1-x^2)(1-x^2)^{n-1} \, dx \\[9pt] &= 2n I_{n-1} - 2n I_n \\[9pt] \implies (2n+1)I_n &= 2n I_{n-1}. \qquad \blacksquare \end{align*}$