Prove using induction

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.