## Chapter - 3, Proofs

### Section - 3.1 - Proof Strategies

### Summary

- A theorem is a statement that has been proven on the basis of previously established statements, such as other theorems—and generally accepted statements, such as axioms.
- A theorem that says that if certain assumptions called the hypotheses of the theorem are true, then some conclusion must also be true.
- The hypothesis and conclusion of a theorem often contains free variables. When values are substituted/assigned for these variables, it is called an instance of the theorem.
- A proof of a theorem is simply a deductive argument whose premises are the hypotheses of the theorem and whose conclusion is the conclusion of the theorem.
- To prove a conclusion of the form of , there can be two strategies:
- Assuming is true, Prove . In this way this strategy transformed the problem of proving to proving . After this transformation, is now the part of the hypothesis.
- Prove contra-positive: assuming is true, prove . Similarly here also problem is transformed from proving to proving .

- Thus multiple transformations can be applied to convert the problem to simpler one.
- At any point of the proof:
*givens*are the set of statements that are known or assumed to be true till that point.*goal*is the final statement that remains to be proven.- Thus at the start of a proof, givens will be the initial hypothesis and goal will be the final conclusion.
- In the course of the proof, the list of hypothesis will increase(during transformation).
- Similarly, conclusion will change during the course of the proof.

- In writing final proof:
- Reasoning used for figuring the the proof are not used/written.
- Steps to justify the conclusions are used/written but no explanations on how the steps were thought of.
- Similarly
*Goals*and*Givens*are also not part of the final proof.

- Explanations are avoided in proofs to maintains the distinction between:
- Explanation of thought process.
- Justifying the conclusions.

- Thus proof of the goal will look as follows:
- Given: ,

Goal - Using strategy-1:
- Scratch work will look as:

Given: ,

Goal . - Final proof will look as:

Suppose is true.

[Proof of ]

Therefore .

- Scratch work will look as:
- Using strategy-2:
- Scratch work will look as:

Given: ,

Goal . - Final proof will look as:
Suppose is false.

[Proof of ]

Therefore .

- Scratch work will look as:

- Given: ,

**Soln1**

**(a)**

Hypothesis:

- is an integer and .
- is not prime.

Conclusion:

is not prime.

- For , hypothesis is true.
- Conclusion is is not prime. This is also true.

**(b)**

- For , hypothesis is true.
- Conclusion is is not prime. This is also true: .

**(c)**

- For , hypothesis is
*not*true. - Thus theorem does not say anything.

**Soln2**

**(a)**

Hypothesis: .

Conclusion: has exactly 2 solutions.

**(b)** are free variables. is not a free variable.

**(c)** Substituting the values: gives . This is true. Thus hypothesis is true.

Conclusion is

Thus $ x = 1 x = 3/2 $$ are two solutions. That means conclusion is also correct.

**(d)** Substituting the values: gives . This is false. Thus hypothesis is false.

Theorem does not say anything as hypothesis is not true.

**Soln3**

Hypothesis:

- is a natural number and .
- is not prime.

Conclusion:

is not prime.

For , Hypothesis is true. Conclusion: , which is a prime number. Thus conclusion is not true.

**Soln4**

Suppose . Then .

Also . Multiplying by

We get . Which gives:

.

Since , it follows that .

**Soln5**

if then and

Thus, the product because product of a positive and negative number is negative.

Expanding the product, we get .

Now since , It follows that .

**Soln6**

if , Multiplying both sides by positive number .

**Soln7**

Suppose . Subtracting from both sides:

.

Multiplying by on both sides:

Simplifying:

Thus we have: .

**Soln8**

We are given that and .

Thus we have

For , we have:

As and suppose , then we get:

Simplifying:

It follows that , or .

**Soln9**

Given that , then adding to both sides:

Dividing both sides by 2:

**Soln10**

We shall prove it by proving contra-positive.

Suppose , we get

Simplifying:

Clearly which is not correct. Thus if , then

Thus if , then

**Soln11**

We shall prove this using contra-positive.
Given that , and

Multiplying , by on both sides:

Suppose that , Multiplying both sides by gives:

Thus we have and , which gives

Or we can say that: .

Thus we proved that if , then .

It follows that if , then .

**Soln12**

Suppose , then

Adding 2 on both sides:

, or , which is same as

Also, given that

Subtracting 3x from both sides:

Thus we have

Simplifying:

, or

**Soln13**

Given that and

Adding both:

Simplifying:

Or

which means .

**Soln14**

Given that

As and , we can apply the theorem: If , then

Thus we have

Also, it is givem that .

Multiplying both sides by -2, and reverting the sign of inequality:

Adding both inequalities:

Or .

**Soln15**

**(a)**

The proof is for: if , then

while the required proof was for: if , then .

**(b)**

Given that

Cross multiplying:

Simplifying:

.

**Soln16**

**(a)**

The issue is that value of is not taken into consideration. As for this value .

**(b)**

If x = -3, then the equation gives , thus theorem is not correct as it says if , then .