Proving inequality for a recurrence

Question

The Question is as Follows:

Define the sequence of numbers Ai by:

A(0) = 2

$A\left(n+1\right)\ =\ \frac{A\left(n\right)}{2}+\frac{1}{A\left(n\right)}$ (for n≥ 1)

Prove that $A\left(n\right)\ \le\ \sqrt{2}+\frac{1}{2^{n}}$ for n >= 0

My Proof:

Proof by induction: P(n): $A\left(n\right)\ \le\ \sqrt{2}+\frac{1}{2^{n}}$

Basecase: n = 0

$A(0) = 2 \le\ \sqrt{2}+\frac{1}{2^{0}}$

So base case is true.

Inductive Step:

Assuming $A\left(n\right)\ \le\ \sqrt{2}+\frac{1}{2^{n}}$ to prove $A\left(n+1\right)\ \le\ \sqrt{2}+\frac{1}{2^{\left(n+1\right)}}.$

By induction hypothesis:

$A\left(n\right)\ \le\ \sqrt{2}+\frac{1}{2^{n}}$

The limit as n goes to infinity A(n) goes to $\sqrt{2}$. it converges to $\sqrt{2}$. This means as n increases A(n) gets smaller and smaller and gets closer to $\sqrt{2}$. This means:

$A\left(n\right)\ \ge\ A\left(n+1\right)$

Which means:

$A\left(n+1\right)\ \le\ \sqrt{2}+\frac{1}{2^{n}}$

We now claim:

$A\left(n+1\right)\ \le\ \sqrt{2}+\frac{1}{2^{\left(n+1\right)}}$

Proof by contradiction: For the sake of contradiction assume the opposite:

$A\left(n+1\right)\ \ge\ \sqrt{2}+\frac{1}{2^{n+1}}$

let n = n - 1

$A\left(n\right)\ \ge\ \sqrt{2}+\frac{1}{2^{n}}$

But this contradicts inductive hypothesis. Therefore:

$A\left(n+1\right)\ \le\ \sqrt{2}+\frac{1}{2^{\left(n+1\right)}}$

Hence Proven.

Is my Proof correct?

Answer 1

Your idea of using induction is correct, but the induction step has mistakes:

• We cannot conclude $A(n)\geq A(n+1)$ solely from $A(n)\leq\sqrt2+2^{-n}$, because this condition only shows the upper bound of $A(n)$ is decreasing, but this does not mean $A(n)$ itself is decreasing.
• The claim is $A(n+1)\leq\sqrt2+2^{-(n+1)}$, so to prove by contradiction we need to assume $A(n+1)>\sqrt2+2^{-(n+1)}$ but not $A(n+1)\geq\sqrt2+2^{-n}$ as in your step.

---

To solve these issues, we need to at least use the recursion. Here are some ideas:

• Change the claim to $\sqrt2<A(n)\leq \sqrt2+2^{-n}$.
• Show that $f(x)=x/2+1/x$ is increasing when $x>\sqrt2$.
• Since $f$ is increasing and $\sqrt2<A(n)\leq\sqrt2+2^{-n}$, we have $$A(n+1)=f(A(n))> f(\sqrt2)\ \text{and similarly}\ A(n+1)\leq f(\sqrt2+2^{-n})$$
• Show that $f(\sqrt2)\geq\sqrt2$.
• Show that $f(\sqrt2+2^{-n})\leq\sqrt2+2^{-(n+1)}$.
• The induction step $\sqrt2<A(n+1)\leq \sqrt2+2^{-(n+1)}$ is then verified.

Answer 2

If you allow yourself to use induction, then why not just look at entire closed form solution. The solution can be found as follows,

$$ a_n=\frac{a_{n-1}}{2}+\frac{1}{a_{n-1}} $$

This is almost in the form of the hyperbolic identity

$$ \coth 2\alpha=\frac{1+\coth^2\alpha}{2\coth\alpha} $$

So, let $b_n=a_n/\sqrt{2}$, which leads to

$$ b_n=\frac{1+b_{n-1}^2}{2b_{n-1}} $$

The let $b_n=\coth(c_n)$, which leads to

$$ \coth (c_n)=\frac{1+\coth^2(c_{n-1})}{2\coth (c_{n-1})}=\coth (2c_{n-1}) $$

Or,

$$ c_n=2c_{n-1}\\ c_n=c_02^n $$

Thus, backing our way to $a_n$,

$$ b_n=\coth(c_n)=\coth(c_02^n)\\ a_=\sqrt{2}b_n=\sqrt{2}\coth(c_02^n) $$

There remain only to determine $c_0$, we find

$$ c_0=\coth^{-1}b_0=\coth^{-1}\frac{a_0}{\sqrt{2}}=\coth^{-1}\frac{\sqrt{2}a_0}{2} $$

so that finally,

$$ a_n=\sqrt{2}\coth\bigg( 2^n\coth^{-1}\frac{\sqrt{2}a_0}{2} \bigg) $$

This should be able to help you prove the original claim.