Discrete Mathematical Structures by Pearson

4-30 Discrete Mathematical Structures

4.9.3 Proof by Counter Example

Example 1 Prove or disprove that n

2

+ 41n + 41 is a prime for every n ∈ N.

To disprove a result, we need only one example for which the implication is false.

Proof: Let P(n) = n

2

+ 41n + 41 is not prime for every n ∈ N.

Putting n = 6, we have

P(6) = 6

2

+ 41 × 6 + 41

 = 36 + 246 + 41 = 323

 = 19 × 17

which shows that it is a composite number.

Hence, P(n) = n

2

+ 41n + 41 is not prime for every n ∈ N.

Example 2 Prove that n

2

- n + 41 is not prime for all n ∈ N.

Proof: Let P(n) = n

2

- n + 41

Putting n = 41

P(41) = (41)

2

- 41 + 41 = (41)

2

= 41 × 41

which is not prime. Hence, n

2

- n + 41 is not prime for all n ∈ N.

Example 3 Prove or disprove the statement that if x and y are real numbers ...