Help with algebraic deduction steps in a proof by induction

[UsableThought]

I'm in the 6th week of a well-known MOOC course created by Kevin Devlin, "Introduction to Mathematical Thinking." I enjoy the course & did well in the first weeks with conditionals and truth tables, etc.; however now that we are entering into proofs, I'm running into trouble with algebra required to understand the example proofs given in the lectures. My high school algebra was a long time ago! So this is a particular lecture example I'm stuck on. I should add that Devlin is not really involved in the course forums anymore, and mentor assistance is available, but spotty; hence I'm posting my question here as well as on the course forum.

1. The problem statement (example proof)

Here is the example proof. I've taken it from the book that Devlin wrote for the course; it's identical to the lecture presentation. I have numbered the steps so that they can be commented on individually.

(0) Theorem: If $x > 0$ then for any $n \in \mathcal{N}$, $$(1 + x)^{n+1} > 1 + (n + 1) x$$

(1) Proof: Let A(n) be the statement $(1 + x)^{n+1} > 1 + (n + 1) x$.

(2) Then $A(1)$ is the statement $$(1 + x)^2 > 1 + 2x$$

(3) which is true by virtue of the binomial expansion $$(1 + x)^2 = 1 + 2x + x^2$$

(4) together with the fact that $x > 0$. The next step is to prove the statement $$(\forall n \in \mathcal{N}) \, [A(n) \Rightarrow A(n+1)]$$

(5) To do this we take an arbitrary (!) $n$ in $\mathcal{N}$ and prove the conditional $$A(n) \Rightarrow A(n+1)$$

(6) To do this we assume $A(n)$ and try to deduce $A(n + 1)$.

(7)We have:
$$\begin{align*}
(1+x)^{n+2} \;&= \;(1 +x)^{n+1}(1+x) \\
&> \;(1 + (n + 1)x)\,(1 + x) \;\; [\text{by } A(n)] \\
&= \;1 + (n+1)x + x + (n+1)x^2 \\
&= \;1 + (n+2)x + (n+1)x^2 \\
&> \;1+(n+2)x \;\; [\text{since } x > 0]
\end{align*}$$

(8)This proves $A(n + 1)$. $\;\; \Box$

Homework Equations

None except the above proof.

3. The attempt at understanding; and what's hanging me up

I've read this part of the book several times; have listened to this part of the lecture video several times; and have copied out the proof and walked myself through each line, asking myself if I understand it. What hangs me up is not the concept of the principle of mathematical induction; I believe I understand that & have no problems or questions about that. And I had no problems with the math for a previous natural number proof in the course that used a simpler formula. It's the algebraic manipulations here in step 7 where I am getting stuck & can't follow.

Here's how I have been describing step 7 to myself: We assume the antecedent in the conditional to be true - that is, $A(n)$ - and are now proceeding to show that the antecedent implies the consequent - that is, $A(n+1)$. We do this step directly; that is, by deduction. More specifically, we change the existing $n$ on both sides of the inequality statement for $A(n)$ to $n + 1$ for the statement $A(n +1)$.

This is all done in the block of 5 aligned statements. Here's how I have been explaining these statements to myself so far:

Line 1, $\;\;(1+x)^{n+2} \; = \;(1 +x)^{n+1}(1+x)$ - this replaces the $n$ in the lefthand side of the statement with $n+1$

Line 2, $\;\;> \;(1 + (n + 1)x)\,(1 + x) \;\; [\text{by } A(n)]$ - this replaces the $n$ in the righthand side of the statement with $n+1$. However I don't understand the reference to $[\text{by } A(n)]$

Line 3, $\;\;= \;1 + (n+1)x + x + (n+1)x^2$ - this expands the righthand side

Line 4, $\;\;= \;1 + (n+2)x + (n+1)x^2$ - factoring the previous line, all but $(n + 1)x^2$

Line 5, $\;\;> \;1+(n+2)x \;\; [\text{since } x > 0]$ - This is what I really don't get. We are now saying this line is less than the previous line. I don't understand how or why; and I don't understand the annotation $[\text{since } x > 0]$ - specifically, why $x > 0$ is suddenly important.

To sum up, I don't understand the annotations in lines 2 and 5 of this block of statements; and I don't understand what is being done in line 5 at all.

I suspect what is throwing me off is that the previous two example proofs I have looked at for induction (one from this course, one from Hammack's The Book of Proof) both had to do with equalities (identities??), not inequalities; and there is something about inequalities that requires or allows a different punch line. I get the feeling that the last two lines of that block of statements have to do with demonstrating an inequality that completes the proof; but although I have a tickle in my mind that says "You're almost there . . . " I can't quite close the gap yet.

 

[BvU]

Line 2: $A(n)$ says $$(1 + x)^{n+1} > 1 + (n + 1) x$$ Now, since $x> 0 \Rightarrow (1+ x)>0\$, we conserve the inequality if we multiply both sides with $(1+x)$:$$(1 + x)^{n+1}(1+x) > \left (1 + (n + 1) x \right ) (1+x) $$ and that's all they mean with "by $A(n)$".
Personally I would find it clearer if the comment would be like "by $A(n)$ and becasue (1+x) > 0 "

Line 5: they are working towards $A(n+1)$ . We are not saying it's less: we are saying " if a=b then a > b - $\varepsilon$ provided $\varepsilon > 0$ " -- and our $(n+1)x^2 > 0$ so we're done.

 

[fresh_42]

I'm in the 6th week of a well-known MOOC course created by Kevin Devlin, "Introduction to Mathematical Thinking." I enjoy the course & did well in the first weeks with conditionals and truth tables, etc.; however now that we are entering into proofs, I'm running into trouble with algebra required to understand the example proofs given in the lectures. My high school algebra was a long time ago! So this is a particular lecture example I'm stuck on. I should add that Devlin is not really involved in the course forums anymore, and mentor assistance is available, but spotty; hence I'm posting my question here as well as on the course forum.

1. The problem statement (example proof)

Here is the example proof. I've taken it from the book that Devlin wrote for the course; it's identical to the lecture presentation. I have numbered the steps so that they can be commented on individually.

(0) Theorem: If $x > 0$ then for any $n \in \mathcal{N}$, $$(1 + x)^{n+1} > 1 + (n + 1) x$$

(1) Proof: Let A(n) be the statement $(1 + x)^{n+1} > 1 + (n + 1) x$.

(2) Then $A(1)$ is the statement $$(1 + x)^2 > 1 + 2x$$

(3) which is true by virtue of the binomial expansion $$(1 + x)^2 = 1 + 2x + x^2$$

(4) together with the fact that $x > 0$. The next step is to prove the statement $$(\forall n \in \mathcal{N}) \, [A(n) \Rightarrow A(n+1)]$$

(5) To do this we take an arbitrary (!) $n$ in $\mathcal{N}$ and prove the conditional $$A(n) \Rightarrow A(n+1)$$

(6) To do this we assume $A(n)$ and try to deduce $A(n + 1)$.

(7)We have:
$$\begin{align*}
(1+x)^{n+2} \;&= \;(1 +x)^{n+1}(1+x) \\
&> \;(1 + (n + 1)x)\,(1 + x) \;\; [\text{by } A(n)] \\
&= \;1 + (n+1)x + x + (n+1)x^2 \\
&= \;1 + (n+2)x + (n+1)x^2 \\
&> \;1+(n+2)x \;\; [\text{since } x > 0]
\end{align*}$$

(8)This proves $A(n + 1)$. $\;\; \Box$

Homework Equations

None except the above proof.

3. The attempt at understanding; and what's hanging me up

I've read this part of the book several times; have listened to this part of the lecture video several times; and have copied out the proof and walked myself through each line, asking myself if I understand it. What hangs me up is not the concept of the principle of mathematical induction; I believe I understand that & have no problems or questions about that. And I had no problems with the math for a previous natural number proof in the course that used a simpler formula. It's the algebraic manipulations here in step 7 where I am getting stuck & can't follow.

Here's how I have been describing step 7 to myself: We assume the antecedent in the conditional to be true - that is, $A(n)$ - and are now proceeding to show that the antecedent implies the consequent - that is, $A(n+1)$. We do this step directly; that is, by deduction. More specifically, we change the existing $n$ on both sides of the inequality statement for $A(n)$ to $n + 1$ for the statement $A(n +1)$.

This is all done in the block of 5 aligned statements. Here's how I have been explaining these statements to myself so far:

Line 1, $\;\;(1+x)^{n+2} \; = \;(1 +x)^{n+1}(1+x)$ - this replaces the $n$ in the lefthand side of the statement with $n+1$

Line 2, $\;\;> \;(1 + (n + 1)x)\,(1 + x) \;\; [\text{by } A(n)]$ - this replaces the $n$ in the righthand side of the statement with $n+1$. However I don't understand the reference to $[\text{by } A(n)]$

"replaces $n$ by $n+1$" isn't a good way to look at it. The statement $A(n)$ is assumed to be true. Now $A(n)$ is defined as $(1+x)^{n+1}>1+(n+1)x$. Therefore we can replace the left factor of $(1 +x)^{n+1}\cdot (1+x)$ by $1+(n+1)x$ and get something, which is smaller, i.e. $(1 +x)^{n+1}\cdot (1+x) > (1+(n+1)x)\cdot (1+x)\,.$ So we only used the assumption, that $A(n)$ is true. (And $(1+x) > 0$ so we didn't have to bother, whether the greater relation turns into a smaller relation.)

As a heuristic mnemonic I like to think of the entire procedure as:

Let's look whether the statement $A(n)$ is true at all. So test it with $n=1$, i.e. $A(1).\,$ If so, then let's pretend, we would have tested it for $A(2)\; , \;A(3)\; , \;A(4)\; , \ldots , A(n-1)\; , \;A(n)$. This is boring, so it looks like it is enough, if we show that we can always prove the next step by the truth of the previous.

O.k., from a pure logical point of view, this might be a little bit problematic, so don't tell it a logician, but it illustrates, what's going on.

Line 3, $\;\;= \;1 + (n+1)x + x + (n+1)x^2$ - this expands the righthand side

Line 4, $\;\;= \;1 + (n+2)x + (n+1)x^2$ - factoring the previous line, all but $(n + 1)x^2$

Line 5, $\;\;> \;1+(n+2)x \;\; [\text{since } x > 0]$ - This is what I really don't get. We are now saying this line is less than the previous line. I don't understand how or why; and I don't understand the annotation $[\text{since } x > 0]$ - specifically, why $x > 0$ is suddenly important.

So far we have $(1+x)^{n+2} \, > \, 1 + (n+2)x + (n+1)x^2$ and we know, that $x > 0$. But then $x^2 > 0$ and also $(n+1)x^2 > 0$.
Therefore if we skip the right summand $[(n+1)x^2]\, ,$ which we know is positive, then we get something smaller out of it:
$1 + (n+2)x + [(n+1)x^2] > 1 + (n+2)x\,.$ Now what is left is to read the entire thing from the start to the end $(1+x)^{n+2} = \ldots > \ldots > 1 +(n+2)x$ and remark, that we have shown this by the assumption, that $A(n)$ is true, the condition $x>0$ and of course $n \in \mathbb{N}.\,$

To sum up, I don't understand the annotations in lines 2 and 5 of this block of statements; and I don't understand what is being done in line 5 at all.

I suspect what is throwing me off is that the previous two example proofs I have looked at for induction (one from this course, one from Hammack's The Book of Proof) both had to do with equalities (identities??), not inequalities; and there is something about inequalities that requires or allows a different punch line. I get the feeling that the last two lines of that block of statements have to do with demonstrating an inequality that completes the proof; but although I have a tickle in my mind that says "You're almost there . . . " I can't quite close the gap yet.

 

[UsableThought]

Line 5: they are working towards A(n+1)A(n+1)A(n+1) . We are not saying it's less: we are saying " if a=b then a > b - εε\varepsilon provided ε>0ε>0\varepsilon > 0 " -- and our (n+1)x2>0(n+1)x2>0(n+1)x^2 > 0 so we're done.

Thanks. I was just coming back to add a revision or additional comment, and saw you had commented. You're addressing what I just learned about, so if I may, I will add a followup question in response.

Basically as soon as I posted, I thought about it some more, and wondered if Hammack might say something in his The Book of Proof about proving statements involving inequalities. Indeed he does, and in the section on proof by induction, no less. He has given a number of examples for equalities; now he turns to inequalities, and introduces these as follows:

The next example illustrates a trick that is occasionally useful. You know that you can add equal quantities to both sides of an equation without violating equality. But don't forget that you can add unequal quantities to both sides of an inequality, as long as the quantity added to the bigger side is bigger than the quantity added to the smaller side. For example, if $x \le y$ and $a \le b$, then $a + x \le y + b$. Similarly, if $x \le y$ and $b$ is positive, then $x \le y + b$.

Two examples later, he gives a proof for a statement quite similar to the one I'm querying about: "If $n \in \mathcal{N}$, then $(1 + x)n \ge 1 + nx$ for all $x \in \mathcal{R}$ with $x > -1$. His last three lines are

$$\begin{align*}
(1 + x)^k(1+x)\; &\ge \;(1 + kx)(1+x) \\
(1 + x)^{k+1} \; &\ge \;1 + x + kx + kx^2 \\
(1 + x)^{k+1} \; &\ge \;1 + (k + 1)x + kx^2
\end{align*}$$

He then says, "The above term $kx^2$ is positive, so removing it from the right-hand side will only make that side smaller. Thus we get $(1+x)^{k+1} \ge 1 + (k + 1)x$. $\Box$

This seems the exact same move as for the proof I'm studying, and the same as what you're describing. I'm going to have to ponder all this. The part I understand at this moment is quite limted - "Yes, you can alter an inequality unequally, so long as the inequality still goes in the same direction". The parts I don't understand quite yet are "how" and "why"; any suggestions on what I should look at elsewhere in algebra to help me grok this?

 

[UsableThought]

"replaces $n$ by $n+1$" isn't a good way to look at it <snip>

Thanks for responding & trying to help. I'm only quoting a snippet of what you have offered; and this is for a reason that has nothing to do with you, but only with me: basically, as someone who hasn't done much algebra in a long, long time, it's almost impossible for me to read a ton of equations and get anything out of it! My mind goes blank.

Pretty much everything I do is self-study except for this MOOC on beginning predicate logic. Since I'm so deficient in algebra (which I only studied in high school, and that was about 40 years ago), and since it is the "not without this" of eventually learning high-school-level physics, as of 2 months ago I had started working my way through Gelfand & Shen's Algebra, which I really like. But then I heard about the Devlin course via a comment on this forum. The course came so highly recommended, and seemed so relevant to how Gelfand and Shen present their exercises (as mini-proofs to demonstrate), that I decided to put the algebra book aside for awhile and come back to it after I finished the MOOC.

The logic course is paced pretty slowly, so I've had enough time in the first 5 weeks to get through whatever math is required without enormous difficulty. Now that we're getting into proofs that require algebra and some very basic number theory, that may change; I may have to scramble pretty hard to keep up. The course is intended for beginning students at university who've never done much abstract thinking before; but it's also intended for anyone who wants to learn a more precise way of thinking. In my case I'm hoping it will help me with the algebra and whatever other math I self-study after that.

But again thanks for your help. If I have a chance I will print out your comment and try to work my way through it slowly.

P.S. By the way, how did you get the LaTeX in your quote of my post to come out correctly? Often it seems that a reply that quotes LaTeX results in raw markup rather than the finished math.

 

[fresh_42]

P.S. By the way, how did you get the LaTeX in your quote of my post to come out correctly? Often it seems that a reply that quotes LaTeX results in raw markup rather than the finished math.

Not quite sure what you mean. I inserted
$\textrm{your text + }$ $\textrm{ [/Quote] }$ $\textrm{ my text }$ $\textrm{ [ Quote] }$ $\textrm{ + your text }$
so technically I stopped your quote and retrieved it again.

Sometimes the reply or quote function turns a LaTex statement like $\textrm{ x \geq 0 }$ into $\textrm{ x>0x>0x \geq 0 }$ in which case I manually correct it. I haven't really figured out when exactly this happens, but I think it doesn't happen, if the LaTex line is inserted in $\textrm{$ code $}$.

 

[BvU]

The parts I don't understand quite yet are "how" and "why"; any suggestions on what I should look at elsewhere in algebra to help me grok this?

My advice would be to try a few examples with numbers and probably then you don't have long to wait until grokking is.

 

[Ray Vickson]

I'm in the 6th week of a well-known MOOC course created by Kevin Devlin, "Introduction to Mathematical Thinking." I enjoy the course & did well in the first weeks with conditionals and truth tables, etc.; however now that we are entering into proofs, I'm running into trouble with algebra required to understand the example proofs given in the lectures. My high school algebra was a long time ago! So this is a particular lecture example I'm stuck on. I should add that Devlin is not really involved in the course forums anymore, and mentor assistance is available, but spotty; hence I'm posting my question here as well as on the course forum.

1. The problem statement (example proof)

Here is the example proof. I've taken it from the book that Devlin wrote for the course; it's identical to the lecture presentation. I have numbered the steps so that they can be commented on individually.

(0) Theorem: If $x > 0$ then for any $n \in \mathcal{N}$, $$(1 + x)^{n+1} > 1 + (n + 1) x$$

Actually, the only role of $x > 0$ is to ensure that $1+x > 0$; the proof put the "since $x > 0$" reason in the wrong place. (So, in fact, all we really need is $x > -1$!)

Since $(1+x)^{n+2} = (1+x)(1+x)^{n+1}$, the two inequalities $1+x > 0$ and $(1+x)^{n+1} > 1 + (n+1)x$ together imply that $(1+x)^{n+2} > (1+x)(1+(n+1)x).$ (Here, we use the fact that if $A > 0$ and $B > C$ then $AB > AC$.) Finally, since $(n+1)x^2 > 0$ we end up having $(1+x)(1+(n+1)x) > 1 + (n+2)x,$ as needed.

 

[fresh_42]

Actually, the only role of $x > 0$ is to ensure that $1+x > 0$; the proof put the "since $x > 0$" reason in the wrong place. (So, in fact, all we really need is $x > -1$!)

We also need $x\neq 0$ to rule out the equality case.

 

[UsableThought]

My advice would be to try a few examples with numbers and probably then you don't have long to wait until grokking is.

Ah, someone who remembers that novel.

I went to find a book cover image and found this - apparently a mod to some Iron Maiden album art. For some reason I like it - 1950s sci-fi feel crossed with spaghetti western vibe.