How to Prove It - Solutions

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