Intereting Posts

Example where Tietze Extension fails?
Intuitive explation for oriented matroids?
Characteristic function of product of normal random variables
Software to find out adjacency matrix of a graph.
Show that $\sqrt{3\sqrt{21} + 8} – \sqrt{3\sqrt{21} – 8} = 1$
If the set of values , for which a function has positive derivative , is dense then is the function increasing?
Finding maclaurin series
Is my proof correct: rank-nullity in a field $K$
constructive canonical form of orthogonal matrix
A linear system of a curve on a K3 surface.
Is “A and B imply C” equivalent to “For all A such that B, C”?
Derivative of a Matrix with respect to a vector
Find the formula for “f”.
Group structure from involutions, exercise devised by Richard Brauer.
Exponential function $ 11^x + 13^x + 17^x – 19^x = 0$

(Fitzpatrick *Advanced Calculus 2e*, Sec. 2.4 #12)

For $c \gt 0$, consider the quadratic equation

$x^2 – x – c = 0, x > 0$.

Define the sequence $\{x_n\}$ recursively by fixing $|x_1| \lt c$ and then, if $n$ is an index for which $x_n$ has been defined, defining

- $\int_{\frac{1}{3}\pi}^{\frac{2}{3}\pi} {\sin(x)\;dx}$ using Riemann sums?
- Is there any known relationship between $\sum_{i=1}^{n} f(i)$ and $\sum_{i=1}^{n} \dfrac {1}{f(i)}$
- Solution of Differential equation $\frac{xdx-ydy}{xdy-ydx} = \sqrt{\frac{1+x^2-y^2}{x^2-y^2}}$
- Difficult improper integral: $\int_0^\infty \frac{x^{23}}{(5x^2+7^2)^{17}}\,\mathrm{d}x$
- Sum of the series $\sum_{n=0}^{\infty} \frac{1}{4^n(2n+1)}$
- Is series $\displaystyle\sum^{\infty}_{n=1}\frac{\cos(nx)}{n^\alpha}$, for $\alpha>0$, convergent?

$$x_{n+1} = \sqrt{c+x_n}$$

Prove that the sequence $\{x_n\}$ converges monotonically to the solution of the above equation.

Note: The answers below might assume $x_1 \gt 0$, but they still work, as we have $x_3 \gt 0$.

This is being repurposed in an effort to cut down on duplicates, see here: Coping with abstract duplicate questions.

and here: List of abstract duplicates.

- Different definitions of trigonometric functions
- How to go about solving this question on differentials?
- Partial Derivative v/s Total Derivative
- Relation between differentiable,continuous and integrable functions.
- A $\sin^n x$ integral
- Closed form for $\int_1^\infty\frac{\operatorname dx}{\operatorname \Gamma(x)}$
- Differentiability of $f(x) = x^2 \sin{\frac{1}{x}}$ and $f'$
- Concerning Carathéodory's criteria of differentiability and a proof that differentiable implies continuous
- Does $\int_{0}^{\infty}{\sin{(\pi{x^2})}\over \sinh{(\pi{x}})\tanh(x\pi)}\mathrm{d}x$ have a simple closed from?
- Why do we need to learn integration techniques?

Assuming that you know that a monotone, bounded sequence converges, you want to do two things. First, show that $\langle x_n:n\in\mathbb{Z}^+\rangle$ is monotone and bounded, and then show that its limit is the positive root of $x^2-x-c=0$.

If $c=x_1=1$, $x_2=\sqrt2>x_1$, while if $c=1$ and $x_1=2$, $x_2=\sqrt3<x_1$, so if the sequence is monotonic, the direction in which it’s monotonic must depend on $c$ and $x_1$. A good first step would be to try to figure out how this dependence works.

The positive root of the quadratic is $\frac12(1+\sqrt{1+4c})$, which I’ll denote by $r$. If $x_n\to r$, as claimed, and does so monotonically, it must be the case that the sequence *increases* monotonically if $x_1<r$ and *decreases* monotonically if $x_1>r$. In the examples in the last paragraph, $r=\frac12(1+\sqrt5)\approx 1.618$, so they behave as predicted.

This suggests that your first step should be to show that if $x_n<r$, then $x_n<x_{n+1}<r$, while if $x_n>r$, $x_n>x_{n+1}>r$; that would be enough to show that $\langle x_n:n\in\mathbb{Z}^+\rangle$ is both monotone and bounded and hence that it has a limit.

Suppose that $0\le x_n<r$; you can easily check that $x_n^2-x_n-c<0$, i.e., that $x_n^2<x_n+c$. On the other hand, $x_{n+1}^2=c+x_n$, so $x_{n+1}^2>x_n^2$, and therefore $x_{n+1}>x_n$. Is it possible that $x_{n+1}\ge r$? That would require that $x_{n+1}^2-x_{n+1}-c\ge 0$ (why?) and hence that $$x_{n+1}^2\ge x_{n+1}+c>x_n+c=x_{n+1}^2\;,$$ which is clearly impossible. Thus, if $0\le x_n<r$, we must have $x_n<x_{n+1}<r$, as desired. I leave the case $x_n>r$ to you.

Once this is done, you still have to show that the limit of the sequence really is $r$. Let $f(x)=\sqrt{c+x}$; clearly $f$ is continuous, so if the sequence converges to $L$, we have $$L=\lim_{n\to\infty}x_n=\lim_{n\to\infty}x_{n+1}=\lim_{n\to\infty}f(x_n)=f(L)\;,$$ and from there it’s trivial to check that $L=r$.

**Added:** Note that although the problem gave us $x_1>0$, this isn’t actually necessary: all that’s needed is that $x_1\ge -c$, so that $x_2$ is defined, since $x_2=\sqrt{c+x_1}\ge 0$ automatically.

Let $k$ be the positive root to your polynomial. Note that $y=x^2-x-c$ is an upward opening parabola with its vertex below the $x$-axis and an initial downward slope. This implies that positive $x$-values less than $k$ produce negative output, while $x$-values greater than $k$ produce positive output.

Note also that all $x_n$ are positive, so it will be acceptable to preserve equalities and inequalities involving $x_n^2$ after taking a square root.

If $x_0=k$, then $x_1^2=c+k=k^2$, so $x_1=k$. The sequence continues like this, and is constant.

If $x_n<k$, then $x_{n+1}^2=c+x_n<c+k=k^2$. So $x_{n+1}<k$. (Similarly if $x_n>k$, then $x_{n+1}>k$.) This establishes that the sequence is either bounded above or below, depending on where $x_0$ is in relation to $k$.

If $x_n<k$, then $x$ is a positive number to the left of the root of your polynomial. $x$-values in this region produce negative output, so $x_n^2-x_n-c<0$. That implies that $x_{n+1}^2=c+x_n>x_n^2$, and so $x_{n+1}>x_n$. (Similarly if $x_n>k$, then $x_{n+1}<x_n$.)

Thus if $x_0<k$ you will have an increasing sequence bounded above. And if $x_0>k$ you will have a decreasing sequence bounded below.

So the limit exists under all possible cases. It’s value has to be a solution to $L=\sqrt{c+L}$. There is only one such solution: $L=k$.

Let $r=\frac {1+\sqrt {1+4c}}2$ be the positive root of the quadratic, so that $r^2=r+c$ and $r\gt 1$

Note that for $n\gt 1$ we have $x_n\gt 0$

Now suppose $r\gt x_n$ so with $x_{n+1}^2=c+x_n$ we have $$r^2-x_{n+1}^2=(r+c)-(c+x_n)=r-x_n\gt 0$$and $$r-x_{n+1}=\frac {r-x_n}{r+x_{n+1}}\lt r-x_n$$

Whence $x_n$ is monotonically increasing, and getting closer to $r$ – the difference reduces at least as fast as $r^{-n}$, so the limit is easy to prove.

On the other hand if $r\lt x_n$ we have $$x_{n+1}^2-r^2=(c+x_n)-(r+c)=x_n-r\gt 0$$and $$x_{n+1}-r=\frac {x_n-r}{x_{n+1}+r}\lt x_n-r$$and the sequence is decreasing and bounded below by $r$, and it is once again easy to prove that this is the limit.

- Some diffuculties trying to compute double sums
- separation properties in Hausdorff, compact spaces
- If $X$ is the set of all group elements of order $p$, and $X$ is finite, then $\langle X \rangle$ is finite
- Evaluation of $ \lim_{x\to 0}\left\lfloor \frac{x^2}{\sin x\cdot \tan x}\right\rfloor$
- Find all $n>1$ such that $\dfrac{2^n+1}{n^2}$ is an integer.
- Why is the quotient map $SL_n(\mathbb{Z})$ to $SL_n(\mathbb{Z}/p\mathbb Z)$ is surjective?
- How to solve the Brioschi quintic in terms of elliptic functions?
- How to prove these two random variables are independent?
- Presentations of subgroups of groups given by presentations
- Probability of rolling a dice 8 times before all numbers are shown.
- Complex Fourier series
- L'hopitals rule with limits
- A collection of sequences that cannot all be made to converge
- Exact sequence of $A$-modules
- Computing $n$ such that $\phi(n) = m$