Proof Using Subsequences

[The Student]

The question starts off as, "Consider the sequence {a(n)} from n=1 to n = ∞, defined inductively by a(1) = 0, and a(n+1) = √(a(n)+ 2) for n ≥ 1. Prove that {an} from n=1 to n = ∞ is increasing". I actually understand everything except for the beginning my professor's answer, and in the beginning of the answer, my professor starts the answer of by putting, "Consider a^2(n+1) − a^2(n) = a(n) + 2 − a^2(n) = − (a^2(n) − a(n) −2) = −(a(n) −2)(a(n) + 1)". Then he puts " Note that a(n) ≥ 0 for all n". It is this last part that confuses me; how does he know that a(n) is ≥ 0 for all n?

 

[pka]

The question starts off as, "Consider the sequence {a(n)} from n=1 to n = ∞, defined inductively by a(1) = 0, and a(n+1) = √(a(n)+ 2) for n ≥ 1. Prove that {an} from n=1 to n = ∞ is increasing". I actually understand everything except for the beginning my professor's answer, and in the beginning of the answer, my professor starts the answer of by putting, "Consider a^2(n+1) − a^2(n) = a(n) + 2 − a^2(n) = − (a^2(n) − a(n) −2) = −(a(n) −2)(a(n) + 1)". Then he puts " Note that a(n) ≥ 0 for all n". It is this last part that confuses me; how does he know that a(n) is ≥ 0 for all n?

It is part of the definition of the sequence: \(\displaystyle a_{n+1}=\sqrt{a_n+2}\ge 0\).

If \(\displaystyle \sqrt t\) is defined then \(\displaystyle \sqrt t\ge 0\).

 

[The Student]

It is part of the definition of the sequence: \(\displaystyle a_{n+1}=\sqrt{a_n+2}\ge 0\).

If \(\displaystyle \sqrt t\) is defined then \(\displaystyle \sqrt t\ge 0\).

It makes sense to me that a(n+1) can't be negative and be defined, but why can 't a(n) be negative here, a(n) = a^2(n+1) - 2?

 

[daon2]

It makes sense to me that a(n+1) can't be negative and be defined, but why can 't a(n) be negative here, a(n) = a^2(n+1) - 2?

As pka said, a_n is defined to be the square root of a real number. a_0 is 0, a_1 is sqrt(2), a_2 is sqrt(sqrt(2)+2), etc. It must be nonnegative by definition. You can prove it by induction if you like but really there is no need: a_0 = 0 is the base case. Assume a_n is >= 0. Then a_{n+1} = sqrt(a_n+2) >= 0.

 

[The Student]

As pka said, a_n is defined to be the square root of a real number. a_0 is 0, a_1 is sqrt(2), a_2 is sqrt(sqrt(2)+2), etc. It must be nonnegative by definition. You can prove it by induction if you like but really there is no need: a_0 = 0 is the base case. Assume a_n is >= 0. Then a_{n+1} = sqrt(a_n+2) >= 0.

Why can't a(3) = -1?

 

[daon2]

Why can't a(3) = -1?

because \(\displaystyle a_3 = \sqrt{\sqrt{\sqrt{2}+2}+2}\)

 

[The Student]

because \(\displaystyle a_3 = \sqrt{\sqrt{\sqrt{2}+2}+2}\)

But how do we know that a(n) is ≥ 0 for all n before we show that it increases from a(1)? He has this work shown at his note, a^2(n+1) − a^2(n) = a(n) + 2 − a^2(n) = − (a^2(n) − a(n) − 2) = − (a(n) −2)(a(n) + 1), but I still don't see how we can know that a(n) is ≥ 0 for all n.

 

[stapel]

But how do we know that a(n) is ≥ 0 for all n....

The first term is non-negative. The second term is found by adding a positive value (being 2) to the first term and then taking the (by definition, positive) square root. The following terms are found by adding a positive value (being 2) and then taking the (by definition, positive) square root.

At what stage in these computations is it possible for any term to be anything other than positive? How do you propose to obtain a negative value from these computations?

 

[The Student]

The first term is non-negative. The second term is found by adding a positive value (being 2) to the first term and then taking the (by definition, positive) square root. The following terms are found by adding a positive value (being 2) and then taking the (by definition, positive) square root.

At what stage in these computations is it possible for any term to be anything other than positive? How do you propose to obtain a negative value from these computations?

In the math that I am taking, everything has to be mentally backed by a proof. We only have to use the basic proofs that we learnt in the first part of the course. Though we don't have to show the intermediate proofs at this point in the course.

So is it possible that he knows that a(n) ≥ 0 for all n by induction? I ask this because we know that a(1) ≥ 0, and we know that a(n+1) ≥ 0. And we know that the only functions that are being used are + and *, so closure under + and * of the natural set applies. My problem now is the function of a.

My problem now is that I can't figure out what a(n) equals as a function, and I am not sure if I have to know what it looks like as a function because we have not even started on functions yet. I just feel totally lost here.

 

[pka]

So is it possible that he knows that a(n) ≥ 0 for all n by induction? I ask this because we know that a(1) ≥ 0, and we know that a(n+1) ≥ 0.
My problem now is the function of a.
My problem now is that I can't figure out what a(n) equals as a function, and I am not sure if I have to know what it looks like as a function because we have not even started on functions yet. I just feel totally lost here.

These are known as Recursive functions.

\(\displaystyle {a_1} = 0\) and if \(\displaystyle n \ge 1,\,\left[ {{a_{n + 1}} = \sqrt {{a_n} + 2} } \right]\).

So \(\displaystyle {a_1} = 0,\,{a_2} = \sqrt 2 ,\,{a_3} = \sqrt {\sqrt 2 + 2} ,\,{a_4} = \sqrt {\sqrt {\sqrt 2 + 2} + 2} , \cdots \)

Now for induction: \(\displaystyle {a_1} < \,{a_2} < 2\) that is \(\displaystyle n=1\) the base case.

Suppose that \(\displaystyle {a_K} < \,{a_{K+1}} < 2\), the inductive case. We are going to add 2 and do the square root.
\(\displaystyle {a_K}+2 < \,{a_{K+1}}+2 < 4\)

\(\displaystyle \sqrt{{a_K}+2} < \,\sqrt{{a_{K+1}}+2} < \sqrt4\)

\(\displaystyle a_{K+1} < \,{a_{K+2}}< 2\)

So for all \(\displaystyle n\) we have proven that \(\displaystyle {a_n} < \,{a_{n+1}} < 2\)

 

[The Student]

These are known as Recursive functions.

\(\displaystyle {a_1} = 0\) and if \(\displaystyle n \ge 1,\,\left[ {{a_{n + 1}} = \sqrt {{a_n} + 2} } \right]\).

So \(\displaystyle {a_1} = 0,\,{a_2} = \sqrt 2 ,\,{a_3} = \sqrt {\sqrt 2 + 2} ,\,{a_4} = \sqrt {\sqrt {\sqrt 2 + 2} + 2} , \cdots \)

Now for induction: \(\displaystyle {a_1} < \,{a_2} < 2\) that is \(\displaystyle n=1\) the base case.

Suppose that \(\displaystyle {a_K} < \,{a_{K+1}} < 2\), the inductive case. We are going to add 2 and do the square root.
\(\displaystyle {a_K}+2 < \,{a_{K+1}}+2 < 4\)

\(\displaystyle \sqrt{{a_K}+2} < \,\sqrt{{a_{K+1}}+2} < \sqrt4\)

\(\displaystyle a_{K+1} < \,{a_{K+2}}< 2\)

So for all \(\displaystyle n\) we have proven that \(\displaystyle {a_n} < \,{a_{n+1}} < 2\)

I just really want to know how he knows that a(n) is ≥ 0 for all n. This is the beginning of an entry level course in pure math at a university, and he must have felt that it was so obvious that he didn't even need to explain how he knows that a(n) ≥ 0 for all n after only giving this information, a^2(n+1) − a^2(n) = a(n) + 2 − a^2(n) = − (a^2(n) − a(n) − 2) = − (a(n) −2)(a(n) + 1) . At this point in the course, I only need to know about the very basic properties of real numbers, induction and the definition of a limit of a sequence.

 

[pka]

I just really want to know how he knows that a(n) is ≥ 0 for all n. This is the beginning of an entry level course in pure math at a university, and he must have felt that it was so obvious that he didn't even need to explain how he knows that a(n) ≥ 0 for all n after only giving this information, a^2(n+1) − a^2(n) = a(n) + 2 − a^2(n) = − (a^2(n) − a(n) − 2) = − (a(n) −2)(a(n) + 1) . At this point in the course, I only need to know about the very basic properties of real numbers, induction and the definition of a limit of a sequence.

Although I am now retired, I have been a chair of a mathematical sciences department at a university.
If you were a student in that department and I were asked to advised you this is what I would tell you.
"Having reviewed your posts in this this thread, I conclude that you are mathematically challenged".
You may well be miss-placed in this course. If I were you, I would seek advise from your department.

 

[daon2]

In the math that I am taking, everything has to be mentally backed by a proof. We only have to use the basic proofs that we learnt in the first part of the course. Though we don't have to show the intermediate proofs at this point in the course.

So is it possible that he knows that a(n) ≥ 0 for all n by induction? I ask this because we know that a(1) ≥ 0, and we know that a(n+1) ≥ 0. And we know that the only functions that are being used are + and *, so closure under + and * of the natural set applies. My problem now is the function of a.

My problem now is that I can't figure out what a(n) equals as a function, and I am not sure if I have to know what it looks like as a function because we have not even started on functions yet. I just feel totally lost here.

Can you not see the pattern?

\(\displaystyle a_4 = \sqrt{2+\sqrt{2+\sqrt{2}}}\)
\(\displaystyle a_5 = \sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2}}}}\)
\(\displaystyle a_6 = \sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2}}}}}\)

The "closed form" of this would be difficult to write without an ellipsis (unless there is some algebra trick I don't see), that is why it is better to define recursively.

I would have once defined myself as mathematically challenged also (and still so in some ways) and found my first real rigorous course to be a big wake-up call. You need to think a lot about the posts in this thread and come to a revelation yourself as opposed to just being told the answer, your question was answered several times without you realizing it. These little revelations, or big "ohhhh" moments make math even enjoyable.

 

[The Student]

Although I am now retired, I have been a chair of a mathematical sciences department at a university.
If you were a student in that department and I were asked to advised you this is what I would tell you.
"Having reviewed your posts in this this thread, I conclude that you are mathematically challenged".
You may well be miss-placed in this course. If I were you, I would seek advise from your department.

I actually know that I am slow to understand this stuff, and I decided to withdraw from the class. However, I was told that math is very important for the area that I want to work in one day and that this kind of math actually will make me even more knowledgeable of the field. So, I asked myself if I want to do something else and settle to save myself years of my life; my answer was simply no. I am 35 years old, and I am very patient.

 

[The Student]

Can you not see the pattern?

\(\displaystyle a_4 = \sqrt{2+\sqrt{2+\sqrt{2}}}\)
\(\displaystyle a_5 = \sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2}}}}\)
\(\displaystyle a_6 = \sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2}}}}}\)

The "closed form" of this would be difficult to write without an ellipsis (unless there is some algebra trick I don't see), that is why it is better to define recursively.

I would have once defined myself as mathematically challenged also (and still so in some ways) and found my first real rigorous course to be a big wake-up call. You need to think a lot about the posts in this thread and come to a revelation yourself as opposed to just being told the answer, your question was answered several times without you realizing it. These little revelations, or big "ohhhh" moments make math even enjoyable.

I completely agree with what you say here. I hate that I have to be handheld like this. It's just that I have spent 3 days meditating on this and cannot for the life of me see how my professor came to his note. He actually told us that this exact question was going to be on the midterm but put differently. Instead of just memorizing the procedure and possibly getting a perfect score on the question but doing so as a fraud, I know that my goals require me to understand this material on the deepest level possible.

So, I am still stuck with my inability to recognize the note from my professor. I know that it must increase from 0, but I don't know how to prove it.

Thank-you for sticking up for me. The other side of me must be a deeply frustrating and helpless side to be on.

 

[daon2]

So, I am still stuck with my inability to recognize the note from my professor. I know that it must increase from 0, but I don't know how to prove it.

That is the purpose of induction. If you show \(\displaystyle a_1 < a_2\) and \(\displaystyle a_{n-1} < a_n\) implies \(\displaystyle a_n < a_{n+1}\) then you have proven it is increasing for all \(\displaystyle n\). Maybe googleing for several examples about induction will help you.

pka did more by showing simultaneously that it is also bounded above. Go step by step through the proof and make sure you understand everything before reading the next line. Sometimes little details may need to be filled in to fit your liking. Proofs done by mathemeticians (especially in textbooks) may sometimes seem hard to follow, sometimes skipping details that seem simple to them or even on purpose for the student to develop the connection. This is how one develops that elusive "mathematical maturity" and will also reveal any big weaknesses you have. It also allows proofs to be shorter and neater.

 

[The Student]

That is the purpose of induction. If you show \(\displaystyle a_1 < a_2\) and \(\displaystyle a_{n-1} < a_n\) implies \(\displaystyle a_n < a_{n+1}\) then you have proven it is increasing for all \(\displaystyle n\). Maybe googleing for several examples about induction will help you.

pka did more by showing simultaneously that it is also bounded above. Go step by step through the proof and make sure you understand everything before reading the next line. Sometimes little details may need to be filled in to fit your liking. Proofs done by mathemeticians (especially in textbooks) may sometimes seem hard to follow, sometimes skipping details that seem simple to them or even on purpose for the student to develop the connection. This is how one develops that elusive "mathematical maturity" and will also reveal any big weaknesses you have. It also allows proofs to be shorter and neater.

I can't even tell you how grateful I am for your last two posts. You have helped me in more ways than just my original question, thank-you so much.

 

[The Student]

Thank-you everyone for helping me.