## 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 $P \to Q$, there can be two strategies:
- Assuming $P$ is true, Prove $Q$. In this way this strategy transformed the problem of proving $P \to Q$ to proving $Q$. After this transformation, $P$ is now the part of the hypothesis.
- Prove contra-positive: assuming $\lnot Q$ is true, prove $\lnot P$. Similarly here also problem is transformed from proving $P \to Q$ to proving $\lnot P$.

- 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 $P \to Q$ will look as follows:
- Given: ,

Goal $P \to Q$ - Using strategy-1:
- Scratch work will look as:

Given: $P$ ,

Goal $Q$. - Final proof will look as:

Suppose $P$ is true.

[Proof of $Q$ ]

Therefore $P \to Q$.

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

Given: $\lnot Q$ ,

Goal $\lnot P$. - Final proof will look as:
Suppose $Q$ is false.

[Proof of $\lnot P$ ]

Therefore $P \to Q$.

- Scratch work will look as:

- Given: ,

**Soln1**

**(a)**

Hypothesis:

- $n$ is an integer and $n > 1$.
- $n$ is not prime.

Conclusion:

$2^n - 1$ is not prime.

- For $n = 6$, hypothesis is true.
- Conclusion is $2^6 - 1 = 63$ is not prime. This is also true.

**(b)**

- For $n = 15$, hypothesis is true.
- Conclusion is $2^{15} - 1 = 32767$ is not prime. This is also true: $32767 = 7 * 4681$.

**(c)**

- For $n = 11$, hypothesis is
*not*true. - Thus theorem does not say anything.

**Soln2**

**(a)**

Hypothesis: $b^2 > 4ac$.

Conclusion: $ax^2 + bx + c = 0$ has exactly 2 solutions.

**(b)** $a,\,b,\, c$ are free variables. $x$ is not a free variable.

**(c)** Substituting the values: $(-5)^2 > 4 \times 2 \times 3$ gives $25 > 24$. This is true. Thus hypothesis is true.

Conclusion is $2x^2 -5x + 3 = 0$

$\quad = 2x^2 -3x -2x + 3 = 0$

$\quad = x(2x - 3) -3(x - 1) = 0$

$\quad = (2x - 3)(x - 1) = 0$

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

**(d)** Substituting the values: $(4)^2 > 4 \times 2 \times 3$ gives $16 > 24$. This is false. Thus hypothesis is false.

Theorem does not say anything as hypothesis is not true.

**Soln3**

Hypothesis:

- $n$ is a natural number and $n > 2$.
- $n$ is not prime.

Conclusion:

$2n + 13$ is not prime.

For $n = 9$, Hypothesis is true. Conclusion: $2 \times 9 + 13 = 31$, which is a prime number. Thus conclusion is not true.

**Soln4**

Suppose $0 < a < b$. Then $b−a > 0$.

Also $a + b > 0$. Multiplying $b−a > 0$ by $b + a$

We get $(b-a)(b+a) > 0$. Which gives:

$b^2 - a^2 > 0$.

Since $b^2 − a^2 > 0$, it follows that $a^2 < b^2$.

**Soln5**

if $a < b < 0$ then $b - a > 0$ and $b + a < 0$

Thus, the product $(b-a)(b+a) < 0$ because product of a positive and negative number is negative.

Expanding the product, we get $b^2 - a^2 < 0$.

Now since $b^2 - a^2 < 0$, It follows that $b^2 < a^2$.

**Soln6**

if $0 < a < b$, Multiplying both sides by positive number $\frac 1 {ab}$.

$\quad = \frac a {ab} < \frac b {ab}$

$\quad = \frac 1 b < \frac 1 a$

**Soln7**

Suppose $a^3 > a$. Subtracting $a$ from both sides:

$\quad a^3 - a > 0$.

Multiplying by $a^2 + 1$ on both sides:

$\quad = (a^3 - a)(a^2 + 1) > 0$

Simplifying:

$\quad = a^5 - a^3 + a^3 - a > 0$

$\quad = a^5 - a > 0$

Thus we have: $a^5 > a$.

**Soln8**

We are given that $A \setminus B \subseteq C \cap D$ and $x \in A$.

Thus we have $\forall y (y \in A \land y \notin B) \to (y in C \land y \in D)$

For $y = x$, we have:

$x \in A \land x \notin B \to (x \in C \land x \in D)$

As $x \in A$ and suppose $x \notin D$, then we get:

$true \land x \notin B \to (x \in C \land false)$

Simplifying:

$x \notin B \to false$

It follows that $x \notin B = false$, or $x \in B$.

**Soln9**

Given that $a < b$, then adding $b$ to both sides:

$a + b < b + b$

$\quad = a + b < 2b$

Dividing both sides by 2:

$\frac {a+b} 2 < b$

**Soln10**

We shall prove it by proving contra-positive.

Suppose $x = 8$, we get

$\frac {\sqrt[3]{8} + 5} {8^2 + 6} = \frac 1 8$

Simplifying:

$\quad \frac {7} {70} = \frac 1 8$

$\quad \frac {1} {10} = \frac 1 8$

Clearly which is not correct. Thus if $x = 8$, then $\frac {\sqrt[3]{x} + 5} {8^2 + 6} \neq \frac 1 x$

Thus if $\frac {\sqrt[3]{x} + 5} {8^2 + 6} = \frac 1 x$, then $x \neq 8$

**Soln11**

We shall prove this using contra-positive.
Given that $0 < a < b$, and $d > 0$

Multiplying $a < b$, by $d$ on both sides: $ad < bd$

Suppose that $c <= d$, Multiplying both sides by $a$ gives: $ac <= ad$

Thus we have $ad < bd$ and $ac <= ad$, which gives $ac <= ad < bd$

Or we can say that: $ac < bd$.

Thus we proved that if $c <= d$, then $ac < bd$.

It follows that if $ac >= bd$, then $c > d$.

**Soln12**

Suppose $x > 1$, then $3x > 3$

Adding 2 on both sides:

$3x + 2 > 5$, or $2 > 5 - 3x$, which is same as $5 - 3x < 2$

Also, given that $3x + 2y \le 5$

Subtracting 3x from both sides:

$2y \le 5 - 3x$

Thus we have $2y \le 5 - 3x < 2$

Simplifying:

$2y < 2$, or $y < 1$

**Soln13**

Given that $x^2 + y = −3$ and $2x − y = 2$

Adding both:

$x^2 + y + 2x - y = -3 + 2$

Simplifying:

$x^2 + 2x + 1 = 0$

Or ${(x+1)}^2 = 0$

which means $x = -1$.

**Soln14**

Given that $x > 3$

As $x > 0$ and $3 > 0$, we can apply the theorem: If $0 < a < b$, then $a^2 < b^2$

Thus we have $x^2 > 9$

Also, it is givem that $y < 2$.

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

$-2y > -4$

Adding both inequalities:
$x^2 - 2y > 9 - 4$

Or $x^2 - 2y > 5$.

**Soln15**

**(a)**

The proof is for: if $x = 7$, then $\frac {2x-5} {x -4} = 3$

while the required proof was for: if $\frac {2x-5} {x -4} = 3$, then $x = 7$.

**(b)**

Given that $\frac {2x-5} {x -4} = 3$

Cross multiplying:

$2x - 5 = 3x - 12$

Simplifying:

$x = 7$.

**Soln16**

**(a)**

The issue is that value of $x = -3$ is not taken into consideration. As for this value $x^2 = 9$.

**(b)**

If x = -3, then the equation gives $y = 1$, thus theorem is not correct as it says if $x \ne 3$, then $y = 0$.