## Chapter 3Notes for 18 August

Notes also available as PDF.

### 3.1 Syllabus and class mechanics

The original syllabus is available.

### 3.2 Introductions

• My background
• Majors in class

### 3.3 Inductive and deductive reasoning

Inductive
making an “educated” guess from prior observations.
Deductive
if premises are satisfied, conclusion follows.

History:

• Old example: Egyptian papyri (1900bc-1800bc)
• Arithmetic table, list of worked problems, used as a text.
• Solve “new” problems by finding similar ones and imitating them.
• Continued through to Greek times (Euclid’s Elements, 300bc)
• Geometry replaced explicit counting.
• Even then, no algebra and little abstraction.
• Algebra:
• 500bc for babylonians!
• 200ad for greeks (Diophantus of Alexandria)
• Spread widely from Persians, Muhammad ibn Mūsā al-khwārizm̄ in 820ad.
• (non-translation of his book’s title gave “algebra”, his name gives “algorithm”)

Mathematics is a combination of both forms of reasoning in no particular order.

Problems to find
inductive
Problems to prove
deductive
Finding a proof
both!

### 3.4 Inductive

 1 + 2 + 3 = 6 = 3 * 4 / 2 1 + 2 + 3 + 4 = 10 = 4 * 5 / 2 ... + 5 = 15 = 5 * 6 / 2

So what is the sum of the first 50?

 50 * 51∕2 = 25 * 51 = 25(25 ⋅ 1) + 250(50 ⋅ 5) + 1000(50 ⋅ 20) = 1275

Integer sequence superseeker from AT&T gives 250 results matching (3,10,15). Some of the sequences are built similarly.

[ NOTE Text uses “probable”. Don’t do that. There’s no probability distribution defined over the choices, so no one choice is more “probable”.]

Only takes a single counterexample to ruin a perfectly wrong theory.

Must be very careful and define what we mean and want. These are the hypotheses or premises.

What is the premise above?

Could we use an extreme case to check possibilites? (What is the sum of 1?)

### 3.5 Deductive

Start with a collection of premises and combine them to reach a result. Note: the rules for combining these also are premises!

Knowing to distinguish a “general principle” from a hypothesis takes time and perspective. That’s part of what we’re covering, but don’t worry much about it now.

Typical patterns:

• if \{premise\} then \{conclusion\}
• \{premises\} therefore… or hence…

Used before algebra (Greek geometry), but algebra really helps.

\eqalignno{ S & = 1 + 2 + 3 + \mathop{\mathop{…}} + n\text{ (Note use of ellipsis)} & & \cr S & = n + (n - 1) + (n - 2) + \mathop{\mathop{…}} + 1\text{ (Reversed, the sum is the same)} & & \cr &\text{(add the two)} & & \cr 2S & = (n + 1) + (n + 1) + (n + 1) + \mathop{\mathop{…}} + (n + 1) = n(n + 1) & & }