# How to Prove It - Solutions

## Chapter - 3, Proofs

### 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$.
• 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$.

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 $% $. 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 $% $.

Soln5

if $% $ then $b - a > 0$ 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 $\frac 1 {ab}$.
$% $
$% $

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 $% $, then adding $b$ to both sides:

$% $
$% $
Dividing both sides by 2:
$% $

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 $% $, and $d > 0$
Multiplying $% $, by $d$ on both sides: $% $
Suppose that $% $, Multiplying both sides by $a$ gives: $% $
Thus we have $% $ and $% $, which gives $% $
Or we can say that: $% $.

Thus we proved that if $% $, then $% $.
It follows that if $ac >= bd$, then $c > d$.

Soln12

Suppose $x > 1$, then $3x > 3$
$3x + 2 > 5$, or $2 > 5 - 3x$, which is same as $% $

Also, given that $3x + 2y \le 5$
Subtracting 3x from both sides:
$2y \le 5 - 3x$

Thus we have $% $
Simplifying:
$% $, or $% $

Soln13

Given that $x^2 + y = −3$ and $2x − y = 2$
$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 $% $, then $% $
Thus we have $x^2 > 9$

Also, it is givem that $% $.
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$.