## Chapter 11Notes for 1 September

Notes also available as PDF.

### 11.1 Review

Two key forms of reasoning in mathematics:

Inductive
Making a guess from prior observations.
Deductive
If premises are satisfied, conclusion follows.

Typically,

problems to find
use inductive reasoning, and
problems to prove
apply deductive reasoning.

But finding a proof is in many ways inductive.

Problem solving so far has been inductive. Take example problems and their solutions. Emulate the solutions on similar problems.

Remember to take great care with the premises in both forms of reasoning!

• Inductive reasoning generalizes from examples.
• If the examples are not appropriate, the result will be incorrect.

Mathematics is representative reasoning.

• We model the real world and represent pieces of it with symbols (numbers, letters, digits, etc.).
• Then we reason about how the symbols interact.
• Only takes a few rules to build a massive system.
• Amazingly, the system often mimics some aspect of the real world.

### 11.2 Proof

2. A few tests, and the guess becomes a conjecture.
3. Once the conjecture is proven, you have a theorem.
• A lemma is a theorem leading to other theorems. Typically a technical result leading to the main theorem.
• A corollary is a subsequent theorem, a simple result after a primary theorem.

Other items:

• Definitions are difficult to define.
• Axioms are fundamental definitions. The classic example:

Two points define a line.

### 11.3 Direct proof

Example 1.16 from the text:

Theorem: If n is a non-negative integer, then {n}^{2} is either a multiple of 4 or one larger than a multiple of 4.

(A whole number is a non-negative integer.)

What are we trying to show? Rephrasing with mathematical symbols, we want to prove that for every non-negative integer n there is some integer k where {n}^{2} = 4k or {n}^{2} = 4k + 1.

To prove this, it doesn’t matter what k is for a given n or which of the two terms apply. For simpler forms like these, however, it’s often useful to construct the result.

Initial exploration.

What else? Build a little table.

 n {n}^{2} form 0 0 4 ⋅ 0 1 1 4 ⋅ 0 + 1 2 4 4 ⋅ 1 3 9 4 ⋅ 2 + 1 4 16 4 ⋅ 4 5 25 4 ⋅ 6 + 1

Recognize a pattern: Evens have one form, odds another. This breaks the problem into two cases.

If n is even, then n = 2i for some integer i. Then {n}^{2} = 4i and k = i.

If n is odd, then n = 2i + 1 for some integer i. Then {n}^{2} = {(2i + 1)}^{2} = 4{i}^{2} + 4i + 1 = 4({i}^{2} + i) + 1 and k = {i}^{2} + i.

To summarize, we have proven the following:

If n is a non-negative integer, then {n}^{2} is either 4i or 4({i}^{2} + i) + 1 for some integer i.

### 11.4 Proof by contrapositives

Sometimes called indirect reasoning, often called proof by contradiction. Purists hate that phrase.

Logically, if p then q is equivalent to if not q then not p. This is the contrapositive.

Thus if you prove that the negation of your conclusion q implies the negation of your hypothesis p, you have proven that your hypothesis p implies the conclusion q. Clear? No? This is why the method often is called proof by contradiction. That route is often easier to understand.

For a demonstration, remember the definition of a prime number. A prime is an integer p≠1 that only can be divided cleanly by 1 and p itself.

Theorem: There are infinitely many prime numbers.

Proof: Suppose there is some largest prime P. Then form the (very large) integer Q = 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅\mathop{\mathop{…}} ⋅ P + 1, one larger than the product of all primes. Now Q is not divisible by any prime, so Q must itself be prime. But Q is larger than P, contradicting the assumption that P is the largest prime. □

What have we actually proven? If there is a largest prime P, then there is a larger prime Q. Thus, there can be no largest prime.

(The symbol □is one traditional ending for a proof. It is used instead of the letters QED, for quod erat demonstrandum. Literally it means “that which was to be demonstrated.”)

The text’s Example 1.17 is another very nice example of this style.

### 11.5 Homework

Groups are fine, turn in your own work. Homework is due in or before class on Mondays.

Write out (briefly) your approach to each problem.

• Prove the formula for the sum of the first n positive integers by mathematical induction. That is, prove 1 + 2 + 3 + \mathrel{⋯} + n = n(n + 1)∕2. The base case here is n = 1. Then show that the nth term transforms into the (n + 1)th term by adding n + 1.

Note that you may email homework. However, I don’t use MicrosoftTM products (e.g. Word), and software packages are notoriously finicky about translating mathematics.

If you’re typing it (which I advise just for practice in whatever tools you use), you likely want to turn in a printout. If you do want to email your submission, please produce a PDF or PostScript document.