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