October 5

Exams not yet fully graded

Key is up – do you want to see it now or after you get your papers back?

Note 1:

In chapter 1 we proved that an argument is value – true in all interpretations by nature of its

internal form or structure, not because of its content or the meaning of its component parts.

Note 2:

We will look at proving arguments that are not universally true, just true in some particular

context.

inductive reasoning – drawing a conclusion based on experience

deductive reasoning – verifying the true or falsity of a conjecture

one counterexample – can disprove a conjectiure

Problem: should we try to prove or disprove?

Prove or disprove the following conjecture: n! <= n²

Disproof by example always works

Proof by example seldom does

Proof by exhaustion is the one exception to the above statement

Section 2.1 three methods

direct proof

prove that for all x and for all y such that x is an even integer and y is an even integer

their product is an even integer

proof by contraposition

n² odd implies that n odd

n not odd implies that n² not odd

proof by contradiction

Section 2.2

mathematical induction

Section 2.4

recursion

Section 2.5

recurrence relations