1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help with algebraic deduction steps in a proof by induction

  1. Feb 14, 2017 #1
    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##

    2. Relevant 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.
     
    Last edited: Feb 14, 2017
  2. jcsd
  3. Feb 14, 2017 #2

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  4. Feb 14, 2017 #3

    fresh_42

    Staff: Mentor

    "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.
    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}.\,##
     
  5. Feb 14, 2017 #4
    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:
    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?
     
  6. Feb 14, 2017 #5
    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.
     
  7. Feb 14, 2017 #6

    fresh_42

    Staff: Mentor

    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 ##}##.
     
  8. Feb 14, 2017 #7

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    My advice would be to try a few examples with numbers and probably then you don't have long to wait until grokking is.
     
  9. Feb 14, 2017 #8

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  10. Feb 14, 2017 #9

    fresh_42

    Staff: Mentor

    We also need ##x\neq 0## to rule out the equality case.
     
  11. Feb 14, 2017 #10
    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.

    iron_maiden_faux_cover_zpslhrcdprl.jpg
     
    Last edited: Feb 14, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Help with algebraic deduction steps in a proof by induction
  1. Deductive proofs (Replies: 4)

Loading...