Questions and Answers about proof by inductionSeptember 16, 2005I will only hand out the first four pages of these questions and answers in class.Print out the rest at home; you can find it at:http://www.math.lsu.edu/ verrill/teaching/discrete2020/Contents1 Questions about proof in general 12 Questions about proof by induction 23 Questions about Assumptions 64 Induction and Sums 75 Where do the formulas for sums come from? 106 Induction problems involving exponents 117 Strong induction and double induction 138 Other examples of proof by induction 149 I don’t understand 1710 Comments on group work 171 Questions about proof in general1. Q: Can you give us a one or two class crash course on “everything we need to know about proofs”?A: This whole course should be giving you lots of things you need to know about proofs. We are startingoff with some strategies for proving results; the first is proof by induction. We will cover more strategieslater. “Everything you need to know” is too much for one or two classes.A few points about theorems and proofs:The statement of a theorem generally has hypothesis and conclusion. You need to assume the hypoth-esis, and show how these lead to the conclusion.A proof is a sequence of true statements, one of which follows from the next via a logical argument. Astatement is a sentence which can be either true or false, e.g., “The sky is orange”, “I like turnips”, and“47 > 90” are all statements (though they might not be true, or provable). We also call sentences like“x is a perfect square” and “x > y” statements, though whether or not they are true depends on what xand y actually are. But “is 5 bigger than 3?”, “x + y”, “the yellow of the sunset”, “Baton Rouge” and“Hello” are not statements.Logical arguments usually follow by using some kind of algebra, or geometry, or some other tools in someparticular area of mathematics.The hypothesis is a statement H, maybe H(x), and the conclusion is also a statement. A typical theoremmight have the form:Theorem: If H(x) holds, then C(x) holds1This theorem can also be written as “H(x) ⇒ C(x)”. For an example, we might haveH(x): “x is a real number and x > 1”C(x): “x2> x.In this case, the theorem is true, which means that whenever H(x) is true C(x) is also true.Some people find it useful to write truth tables. Here’s one with H(x) and C(x) as above.H(x) C(x) H(x) ⇒ C(x) examples with these truth valuesT T T x = 7T F F no examples, since for this case H(x) ⇒ C(x) is always trueF F T x = 0F F T x = −5Here T means “true”, and F means “false”.A truth table can help in understanding the logic of a proof, but a truth table is not a proof.Sometimes it might be necessary to use more complicated logical constructions, and we’ll talk a bit aboutthis when we cover another proof strategy, called “proof by contradiction”.We will talk more about proofs as the course progresses.Meanwhile, there are some useful web pages about proofs. Have a look at:http://www.math.ucsd.edu/∼ebender/proofs.htmlhttp://pass.maths.org.uk/issue7/features/proof1/index-gifd.htmlhttp://en.wikipedia.org/wiki/Mathematicalinductionhttp://www.math.csusb.edu/notes/logic/lognot/node1.html2. Q: Is there a certain set of words to be used when writing proofs? Like a standard example you couldshow us, where we could just go back and fill in the blanks of a particular problem?A: There are many different kinds of proofs, so it would be possible to give a “fill in the blanks” for somekinds, but there are too many to give such a form for all proofs. However, for proof by induction for sums,we have given a “fill in the blanks” method in class.3. Q: Do you always use words in proving or is there a shorter way to prove it by only numbers?A: Usually you have to use words and numbers. Quite often the words can be minimal, since you canassume the reader knows what proof by induction is, so you might just write, “Proof by induction”, “basecase:” “induction step”, and “QED”.Writing clearly is very important, especially for anyone who wants to become a teacher.4. Q: After doing base cases and finding patterns, I don’t know how to use induction to prove a case. I don’tknow how to put answers in mathematical terms.A: I think this is a question of practice and experience. The more examples you read through, and themore exercises you try, the easier this will become. There are quite a lot of examples in this hand out.2 Questions about proof by induction5. Q: What exactly is proof by induction? We are learning how to solve, but what is the formal definition?A: Let P (n) be a statement involving a positive whole number. (See Question 1 for a definition of astatement; see the previous hand out on induction for three examples.)A proof by induction of the statement “P (n) for all n ≥ n0” is a proof that(a) demonstrates that P (n0) is true (this is called the “base case”)(b) Shows how to prove P (n) ⇒ P (n + 1) (this is called the “induction step”)2This is a proof of the result for all n. E.g., if you take any given value of n, e.g., n = 17, then, supposingthat n0= 3.By substituting n = 3 into (b), we have P(3) ⇒ P (4)By substituting n = 4 into (b), we have P(4) ⇒ P (5)By substituting n = 4 into (b), we have P(5) ⇒ P (6)And so on, so we getP (3) ⇒ P (4) ⇒ P (5) ⇒ P (6) ⇒ P (7) ⇒ P (8) ⇒ P (9) ⇒ P (10) ⇒P (11) ⇒ P (12) ⇒ P (13) ⇒ P (14) ⇒ P (15) ⇒ P (16) ⇒ P (17)So, because we showed that P(3) is true (step (a), the base case), this means that P (17) is true.6. Q: How can you prove something by induction?Do you mean in general, or in particular?See Question 5 for a formal description.The idea of proof by induction can be written even more formally, as follows, where P (n) is a statementinvolving an integer n.³“P (n0)” ∧ “P (n) ⇒ P (n + 1)∀n ≥ n0”´⇒ “P (n)∀n ≥ n0”Here, ∧ means “and”, and ∀ means “for all”, and ⇒ means “implies”.If this doesn’t mean anything to you, just use the definition at the the beginning of this answer.There are examples of proof by induction on the next few pages.Note that “proof by induction” is not the same as “inductive reasoning”.“Inductive reasoning”, also called the “inductive method” or the “Scientific Method” takes many manyexamples, and uses these to make a guess about what a result might be.Inductive reasoning can be a very