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?

Thanks for your time!

  • $\begingroup$ $\sqrt2<2\implies\sqrt{2+\sqrt2}<\sqrt{2+2}=2$, and $a_k<2\implies \sqrt{2+a_k}<\sqrt{2+2}=2$ $\endgroup$ – 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?

| cite | improve this answer | |
  • $\begingroup$ 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! $\endgroup$ – Jeel Shah Apr 20 '15 at 14:56
  • 1
    $\begingroup$ 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... $\endgroup$ – 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.

| cite | improve this answer | |

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$"

| cite | improve this answer | |
  • $\begingroup$ 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$). $\endgroup$ – A.P. Apr 20 '15 at 14:03
  • $\begingroup$ @A.P. But OP does not ever prove that the sequence is strictly increasing. $\endgroup$ – MCT Apr 20 '15 at 14:05
  • $\begingroup$ 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. $\endgroup$ – A.P. Apr 20 '15 at 14:08
  • $\begingroup$ @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. $\endgroup$ – 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 $$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.