# Solution verification: Prove by induction that $a_1 = \sqrt{2} , a_{n+1} = \sqrt{2 + a_n}$ is increasing and bounded by $2$

I have the following recursive relation (sequence):

\begin{align} a_1 = \sqrt{2}, \quad a_{n+1} = \sqrt{2 + a_n} \end{align}

My Try:

I'm a little skeptical of my manipulations near the end but it looks like it works out.

Base Case: Let $n=1$ then \begin{align} &a_2 = \sqrt{2 + a_1} \\ &a_2 < 2 \\ &\sqrt{2 + \sqrt{2}} < 2 \end{align} The base case holds.

Induction hypothesis: Let $n=k$

$$a_1 = \sqrt{2} \quad a_{k+1} = \sqrt{2 + a_k} \quad a_{k+1} = \sqrt{2}$$

Induction Step:

Now we have to prove that $a_{k+2} < 2$. Let $n=k+1$. \begin{align} a_{k+2} &= \sqrt{2 + a_{k+1}} \\ \implies a_{k+2} &= \sqrt{2 + \sqrt{2 + a_k}} \\ \end{align}

Now we have to show that $a_{k+2} < 2$. \begin{align} a_{k+2} &< 2\\ \sqrt{2 + \sqrt{2 + a_k}} &< 2\\ 2 + \sqrt{2 + a_k} &< 4 \\ \sqrt{2 + a_k} &< 2 \\ \end{align} Q.E.D

Are my steps correct?

• $\sqrt2<2\implies\sqrt{2+\sqrt2}<\sqrt{2+2}=2$, and $a_k<2\implies \sqrt{2+a_k}<\sqrt{2+2}=2$ – Yves Daoust Apr 20 '15 at 13:48

The title mentions proving that $(a_n)$ is increasing, but you don't seem to handle that.

More importantly, although you understand that the key to proving bounded-ness is $\sqrt{2+\sqrt2}<2$, you really need to work on the "style" of your induction proof. See for instance my answer here : Proof by Induction:

By writing the induction steps in full length and correctly, you should immediately see what's ok or wrong in your proof.

Can I suggest that you should at least really revise the part where you write "Let $n = k$". What does it mean? Both $n$ and $k$ are silent variables...

What you want to say is rather: let $n$ be an integer $\ge 2$ and let's assume that $P_n$ is true. Then blah, blah, which shows that $P_n \implies P_{n+1}$.

PS: for any induction proof, I can't recommend enough to write down in full length what the property $P_n$ is and, why not, the domain of $n$. Here that would be (formatting being a matter of taste):

$$(n \ge 2)\quad P_n \; : \; 0 < a_n < 2 \quad\text{and}\quad a_n > a_{n-1}$$

That should make checking your initial case and your general case more "mechanical" (and thus easier) - it also makes your TA/exam corrector's life easier.

Late edit: I have tried to provide some basic help on induction proof writing here : Proof writing: how to write a clear induction proof?

• Thanks for the answer, Alex. So, is my line of reasoning correct and the format/style is incorrect or is everything incorrect including my line of reasoning? Thanks! – Jeel Shah Apr 20 '15 at 14:56
• In its current form, I'd say both :( but let's be clear, you probably have the right intuition, you just need to organize your ideas properly. I recommend to take your notes or book, look at the definition of a proof by induction, and replicate it as closely as possible with the present problem. As long as you don't feel 100% comfortable with a concept, don't hesitate to be scholar... – Alexandre Halm Apr 20 '15 at 20:20

I think you're making a bit of confusion. On one hand you are never proving that the sequence is increasing, on the other hand your argument is a bit too complicated. Here is how I would go about proving it:

• $\mathbf{n = 1}$: First note that $a_1 < a_2$ if and only if $$a_1^2 = 2 < 2 + \sqrt{2} = a_2^2$$ which is clearly true. Further, $a_2 < 2$ because $2 + \sqrt{2} < 4$.

• Assume that $a_{n-1} < a_n < 2$. Then we need to prove that $a_n < a_{n+1} < 2$. For the first part note that $a_n < a_{n+1}$ is equivalent to $a_n^2 < 2 + a_n$, i.e. $$a_n (a_n - 1) < 2$$ which is true because $a_n < 2$ implies $a_n - 1 < 1$. For the second part, note that $a_{n+1} < 2$ is equivalent to $$2 + a_n < 4$$ which is true because $a_n < 2$ by hypothesis.

Your base case and inductive step are both overly complicated.

Base case: We have $a_1 = \sqrt{2}$, which is less than $2$.

Inductive step: Assume we have $a_k < 2$

Now $a_{k+1} = \sqrt{2 + a_k} < \sqrt{2 + \sqrt{2}} < \sqrt{2 + 2} = 2$.

It may also be useful to remark that the sequence is strictly positive, so it is also bounded below.

The error you are making is that your base case proves $a_2$ but it should prove $a_1$ and your inductive step proves $a_{k+2}$ when you should be proving $a_{k+1}$.

Also, I'm a bit confused by your inductive step. There's no need to write the definition of the sequence in the inductive step and I'm confused why you have $a_{k+1} = \sqrt{2}$. Did you mean $a_{k+1} < \sqrt{2}$? Because if so, your inductive step (if you are assuming it for $n = k$) should say $a_k < \sqrt{2}$. Indeed, the statement you are trying to prove is $\{P_k : \text{each } a_k \text{ is bounded by } 2\}$. So in the inductive step you assume $P_n$ which is "$a_n$ is bounded by $2$"

• For the base case he needs to prove that $a_1 < a_2$, so starting by $n = 1$ is fine (because this will immediately imply $a_1 < 2$). – A.P. Apr 20 '15 at 14:03
• @A.P. But OP does not ever prove that the sequence is strictly increasing. – MCT Apr 20 '15 at 14:05
• I'm perfectly aware of that (as I also stated in my answer). I am referring to "the error you are making is that your base case proves a_2 but it should prove a_1". Also, proving the statement for $a_{k+2}$ assuming it true for $a_{k+1},a_k$ is certainly overzealous, but not wrong per se. – A.P. Apr 20 '15 at 14:08
• @A.P. But that's exactly my point. I didn't mean to imply it is wrong, but only that it is way too overcomplicated to prove the way OP is, and I assume that this is a result of OP's misunderstanding of his task. – MCT Apr 20 '15 at 14:10

$b_i:= a_i^2$ Then $$b_1=2,\ b_{n+1}=2+\sqrt{b_{n}}$$

Show that $b_i$ is an increasing sequence bounded by $4$ :

(1) $b_1< 4$ If $b_n<4$ then $b_{n+1}=2+\sqrt{b_n}< 2+2=4$.

(2) $b_2=2+\sqrt{2} > b_1$ If $b_n>b_{n-1}$ then $$b_{n+1}=2+\sqrt{b_n} > 2+\sqrt{b_{n-1}}=b_n$$