# Prove using induction

I have this math problem I'm kind of stuck on. Here's the question:

Define a sequences of real number with the definitions \begin{align*} x_1 & = 3 \\ x_n &= \sqrt{2 x_{n-1}+1} \text{ for n \ge 2}. \end{align*} Prove by induction that $x_n \ge x_{n+1}$.

I know that for induction you have to check the initial case. I set $G(n): x \ge x_{n+1}$. For my initial case I check $G(2)$. I get $\sqrt{7} > \sqrt{2\sqrt{7}+1}$, which is true. I know assume that $G(k)$ is true for some k $\in \mathbb{Z}^+, k \ge 2$. So I get my induction assumption $G(k): x_k \ge x_{k+1}$. Now I show that $G(k+1)$ is also true. So I have $G(k+1) = x_{k+1}\ge x_{k+2}$. I am not sure where to go from here. Thanks.

Simply use the definition of $x_{k+1}$.

We have to show $x_{k+1}\geq x_{k+2}$.

By definition, this is equivalent to

$\sqrt{2x_k+1}\geq \sqrt{2x_{k+1}+1}$

Take the square this inequality: $2x_k+1\geq 2x_{k+1}+1$.

This is true by the induction assumption.

• That line of reasoning doesn't work unless $x_1\le 1+\sqrt{2}$. And nowhere in your answer did you ever refer to the initial value of the sequence. If $x_1=1$, then $x_2=\sqrt{3}>1=x_1$. In fact, we have $x_{n+1}\ge x_n$ if $x_1\le 1+\sqrt{2}$. So, I suggest that you augment this answer. ;-) Oct 8, 2015 at 0:58
• @Dr.MV, the OP specifies the initial seed $x_1 = 3$. Additionally, I do not follow why this line of reasoning does not work unless $x_1 \leq 1 + \sqrt{2}$. Care to elaborate a bit? Oct 8, 2015 at 1:43
• Please ignore my last comment, I have just seen Spenser's answer. Oct 8, 2015 at 1:45
• @Dr.MV, is this solution incorrect?
– KFC
Oct 8, 2015 at 2:24
• @KFC Yes, but with a slight modification/added explanation. Oct 8, 2015 at 2:56

Since $x_i\geq 1$, we have $$x_{n+1}\le x_n\iff 2x_n+1\leq x_n^2\iff 2\le(x_n-1)^2\iff x_n\geq1+\sqrt{2}.$$ Now, show the latter by induction: $$x_{n+1}=\sqrt{2x_n+1}\ge \sqrt{3+2\sqrt{2}}= 1+\sqrt{2},$$ where the last equality follows since $$(1+\sqrt{2})^2=1+2\sqrt{2}+2=3+2\sqrt{2}.$$ Note: This also shows that $x_n$ is bounded below and hence converges by the Monotone Convergence Theorem.

We have the recurrence relationship

$$x_{n}=\sqrt{2x_{n-1}+1} \tag 1$$

with $x_1=3$. For the base case, we have for $n=2$, $x_2=\sqrt{7}<3=x_1$.

Next we assume that $(1)$ is true for some $k$ so that

$$x_{k}=\sqrt{2x_{k-1}+1}$$

Thus, we have

$$x_{k+1}-x_k=\sqrt{2x_k+1}-x_k=\frac{2-(x_k-1)^2}{\sqrt{2x_k+1}+x_k} \tag 2$$

CASE $1$:

If $x_k\le 1+\sqrt{2}$, then $x_{k+1}=\sqrt{2x_k+1}\le \sqrt{3+2\sqrt{2}}=1+\sqrt{2}$. Therefore, if $x_1\le 1+\sqrt{2}$, then $x_k\le 1+\sqrt{2}$. From $(2)$, we see then that if $x_1\le 1+\sqrt{2}$, then $x_{k+1}\ge x_k$.

CASE $2$:

If $x_k\ge 1+\sqrt{2}$, then $x_{k+1}=\sqrt{2x_k+1} \ge \sqrt{3+2\sqrt{2}}=1+\sqrt{2}$. Therefore, if $x_1\ge 1+\sqrt{2}$, then $x_k\ge 1+\sqrt{2}$. From $(2)$, we see then that if $x_1\ge 1+\sqrt{2}$, then $x_{k+1}\le x_k$.

And this shows that if $x_1=3$, then $x_n$ is decreasing.

• Please let me know how I can improve my answer. I really want to give you the best answer I can. If the answer was not useful to warrant an up vote, I am happy to delete. Nov 11, 2015 at 19:04