0.2 Proof techniques

Solution.

1. Assume the hypothesis, and unfold it. Let $n$ be odd. Then $n = 2k + 1$ for some integer $k$. Definition of odd. The letter $k$ names the integer the definition promises.
2. Compute what the conclusion is about. $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1$. Algebra on the expression we have.
3. Rewrite in the form the conclusion needs. $n^2 = 2(2k^2 + 2k) + 1$. ‘Odd’ means $2(\text{integer}) + 1$, so we factor a 2 out of everything except the 1.
4. Check the bracket is an integer. $2k^2 + 2k$ is an integer because $k$ is. Sums and products of integers are integers. Without this line the form proves nothing.

Answer. $n^2 = 2m + 1$ with $m = 2k^2 + 2k$ an integer, so $n^2$ is odd. $\blacksquare$

Solution.

1. Assume the hypothesis and unfold it. Let $a, b, c$ be integers with $a \mid b$ and $a \mid c$. Then $b = aj$ and $c = ak$ for some integers $j$ and $k$. Definition of divides. Two different letters, $j$ and $k$, because the two multipliers need not be equal.
2. Compute the thing the conclusion is about. $b + c = aj + ak = a(j + k)$. The conclusion asks for $b + c = a \cdot (\text{integer})$, so we factor $a$ out.
3. Check the bracket is an integer. $j + k$ is an integer because $j$ and $k$ are. Sums of integers are integers. Without this the form proves nothing.

Answer. $b + c = a(j + k)$ with $j + k$ an integer, so $a \mid (b + c)$. $\blacksquare$

Solution.

1. Notice the direct route is awkward. "$n^2 = 2k$" does not easily tell you anything about $n$ (taking square roots leaves the integers). Spotting a stuck start is the signal to switch technique.
2. Write the contrapositive. If $n$ is not even (so odd), then $n^2$ is not even (so odd). For integers, ‘not even’ is the same as ‘odd’.
3. Prove it directly. That is exactly the previous worked example: odd $n$ gives odd $n^2$. Reuse a proved result.

Answer. The contrapositive is true, so the statement is true. $\blacksquare$

Solution.

1. Try the direct start. Assume $ab = 2k$. This says nothing about $a$ or $b$ alone, and we cannot split $2k$ into a piece for each. The hypothesis is not concrete, which is the signal to try the contrapositive.
2. Write the contrapositive using the negation rules. The conclusion is ”$a$ even OR $b$ even”. Its negation is ”$a$ not even AND $b$ not even” (De Morgan, rule 2 of 0.1). So the contrapositive is: if $a$ and $b$ are both odd, then $ab$ is odd. Negating a conclusion with ‘or’ gives ‘and’, and for integers ‘not even’ means ‘odd’.
3. Unfold the new hypothesis. $a = 2j + 1$ and $b = 2k + 1$ for integers $j, k$. Now we have two concrete formulas to compute with.
4. Multiply and aim for the odd form. $ab = 4jk + 2j + 2k + 1 = 2(2jk + j + k) + 1$. Odd means $2(\text{integer}) + 1$, so we factor 2 out of everything except the 1.
5. Check the bracket is an integer. $2jk + j + k$ is an integer because $j$ and $k$ are. Sums and products of integers are integers.

Answer. The contrapositive is true, so the original statement is true. $\blacksquare$

Solution.

1. Assume the negation, exactly. Suppose $3n + 4$ is odd AND $n - 3$ is odd. The negation of ‘if P then Q’ is ‘P and not Q’. Both facts are now available.
2. Unfold both. $3n + 4 = 2a + 1$ and $n - 3 = 2b + 1$ for some integers $a, b$. Definition of odd, with a different letter for each, since they need not be equal.
3. Express $n$ from the simpler one. $n = 2b + 4$. The second equation pins $n$ down.
4. Substitute into the other. $3n + 4 = 3(2b + 4) + 4 = 6b + 16 = 2(3b + 8)$. Now compute $3n + 4$ a second way.
5. Compare the two forms. $3n + 4$ is $2(3b + 8)$, which is even, and also $2a + 1$, which is odd. Compare forms. Do not divide by 2 or solve for $a$.
6. Contradiction. No integer is both even and odd. An even number leaves remainder 0 on division by 2, an odd one remainder 1 (the division algorithm, 0.5).

Answer. The assumption is impossible, so the statement is true. $\blacksquare$ (A direct proof also works: if $3n + 4$ is odd, then $3n$ is odd, so $n$ is odd, so $n - 3$ is even. Contradiction is not the only way; it is one tool.)

Solution.

1. Write the assumption, exactly. Suppose $x$ is irrational AND $x + 1$ is rational. The negation of ‘if P then Q’ is ‘P and not Q’. Not-Q here is ‘rational’, since ‘not irrational’ means rational.
2. Unfold the rational one. $x + 1 = p/q$ for integers $p, q$ with $q \ne 0$. Definition of rational. This is the concrete fact we were missing in a direct proof.
3. Solve for $x$. $x = p/q - 1 = (p - q)/q$. Subtract 1 and use a common denominator.
4. Check the target form. $p - q$ is an integer and $q$ is a non-zero integer. So $x$ is rational. That is exactly the definition of rational, including the condition $q \ne 0$.
5. State the contradiction. $x$ is rational and $x$ is irrational. No number is both, and step 1 gave us ‘irrational’.

Answer. The assumption is impossible, so if $x$ is irrational then $x + 1$ is irrational. $\blacksquare$

Solution.

1. Choose cases that cover everything. Every integer is even or odd. The cases must leave nothing out; say why they are exhaustive.
2. Case $n$ even. $n = 2k$, so $n^2 + n = 4k^2 + 2k = 2(2k^2 + k)$, even. Unfold and factor out 2.
3. Case $n$ odd. $n = 2k + 1$, so $n^2 + n = (4k^2 + 4k + 1) + (2k + 1) = 2(2k^2 + 3k + 1)$, even. Same method.

Answer. Even in both cases, hence for every integer. $\blacksquare$ (A one-line proof also exists: $n^2 + n = n(n + 1)$ is a product of two consecutive integers, one of which is even. Looking for structure often removes the need for cases.)

Solution.

1. State $S(n)$. $S(n)$: ”$7^n - 1 = 6m$ for some integer $m$”. Divisibility has to be unfolded into an equation before we can compute with it.
2. Base case. $n = 1$: $7^1 - 1 = 6 = 6 \cdot 1$. $S(1)$ is true, so the first domino falls.
3. Assume $S(k)$ for one fixed $k \ge 1$. $7^k - 1 = 6m$ with $m$ an integer. This is the induction hypothesis. We assume only the case $k$, not all cases.
4. Rewrite the case $k + 1$ so that $7^k - 1$ appears. $7^{k+1} - 1 = 7 \cdot 7^k - 1 = 7(7^k - 1) + 7 - 1 = 7(7^k - 1) + 6$. We add and subtract 7 to create the bracket $7^k - 1$, because that is the quantity the hypothesis talks about.
5. Substitute the hypothesis and factor. $7^{k+1} - 1 = 7 \cdot 6m + 6 = 6(7m + 1)$. Replace $7^k - 1$ by $6m$. Both terms now contain 6, so it factors out.
6. Check the bracket. $7m + 1$ is an integer. The form $6 \cdot (\text{integer})$ is what $S(k+1)$ demands.

Answer. $S(1)$ is true and $S(k) \Rightarrow S(k+1)$ for every $k \ge 1$, so $6 \mid 7^n - 1$ for all $n \ge 1$. $\blacksquare$ (Check: $7^2 - 1 = 48 = 6 \cdot 8$, and $7 \cdot 1 + 1 = 8$ with $m = 1$ from $n = 1$.)

Solution.

1. Find where the claim starts being true. $1! = 1 < 2$, $2! = 2 < 4$, $3! = 6 < 8$, but $4! = 24 > 16$. The claim is false for $n = 1, 2, 3$. The base case must be a true case, so it is $n = 4$.
2. Base case. $4! = 24 > 16 = 2^4$. The first domino.
3. Assume $S(k)$ for a fixed $k \ge 4$. $k! > 2^k$. The induction hypothesis.
4. Build the case $k + 1$ from the hypothesis. $(k+1)! = (k+1)\cdot k! > (k+1) \cdot 2^k$. Factorials grow by multiplying by the next number, and the hypothesis lets us replace $k!$ by the smaller $2^k$. Multiplying a strict inequality by the positive number $k + 1$ keeps its direction.
5. Compare with the target $2^{k+1}$. Since $k \ge 4$, we have $k + 1 \ge 5 > 2$, so $(k+1) \cdot 2^k > 2 \cdot 2^k = 2^{k+1}$. Here is where $k \ge 4$ is used. It makes the multiplier at least 2.

Answer. $(k+1)! > 2^{k+1}$, so the step works for every $k \ge 4$. With the base case, $n! > 2^n$ for all $n \ge 4$. $\blacksquare$

Solution.

1. Find where the claim starts to hold. Compare $2^n$ with $n^2$: for $n = 2$ it is $4$ against $4$ (equal, so not “greater”), for $n = 3$ it is $8$ against $9$, for $n = 4$ it is $16$ against $16$, and for $n = 5$ it is $32$ against $25$. The base case must be a true case from which the step works. The inequality fails at 2, 3 and 4, so we start at 5.
2. Base case. $n = 5$: $32 > 25$. The first domino.
3. Assume $S(k)$ for a fixed $k \ge 5$. $2^k > k^2$. The induction hypothesis.
4. Start from the case $k + 1$ and use the hypothesis. $2^{k+1} = 2 \cdot 2^k > 2k^2$. Doubling both sides of the hypothesis.
5. Compare $2k^2$ with the target $(k+1)^2$. $2k^2 - (k+1)^2 = k^2 - 2k - 1 = (k-1)^2 - 2$, which is positive for $k \ge 3$, in particular for $k \ge 5$. We need $2k^2 \ge (k+1)^2$. This is where the size of $k$ is used.
6. Chain the inequalities. $2^{k+1} > 2k^2 \ge (k+1)^2$. The first step is the hypothesis, the second is step 5.

Answer. The step holds for every $k \ge 5$ and the base case holds, so $2^n > n^2$ for all $n \ge 5$. $\blacksquare$

Solution.

1. Check the base case. If $\max(a, b) = 1$ then $a$ and $b$ are positive integers at most 1, so both are 1. The base case is fine, so the flaw is in the step.
2. Check the step with the smallest numbers. Take $k = 1$, $a = 2$, $b = 1$, so $\max(a, b) = 2 = k + 1$. Then $a - 1 = 1$ and $b - 1 = 0$. Test the step on its first real case. A false conclusion must break somewhere, and small cases break first.
3. Find the broken hypothesis. The induction hypothesis speaks only about POSITIVE integers, and $0$ is not positive. The step used the hypothesis on a pair outside its range.
4. Conclude. The step "$S(k) \Rightarrow S(k+1)$" is false for $k = 1$. A valid induction needs the step for EVERY $k \ge 1$, including the first.

Answer. The inductive step fails when one of $a - 1$, $b - 1$ is 0, so the proof is invalid. A proof by induction is only as good as its weakest step.

Solution.

1. Check the algebra of the step. $\frac{(2k+1)^2}{8} + (k+1) = \frac{4k^2 + 4k + 1 + 8k + 8}{8} = \frac{4k^2 + 12k + 9}{8} = \frac{(2k+3)^2}{8}$. The step is correct. We should not assume a proof is wrong in the place we first look.
2. Look for the missing part. No base case was checked. An induction needs both the base case and the step.
3. Test the base case. At $n = 1$: left side $1$, right side $\frac{3^2}{8} = \frac98$. These differ. The formula fails at $n = 1$, so the first domino never falls.

Answer. The step is valid and the claim is false, because the base case fails. The true formula is $\frac{n(n+1)}{2}$, which differs from $\frac{(2n+1)^2}{8}$ by the constant $\frac18$.

Solution.

1. Set up strong induction from 2. $S(n)$: ”$n$ is a prime or a product of primes”, for $n \ge 2$. Base case $n = 2$: 2 is prime. Induction can start at any integer, as long as the base case matches.
2. Assume $S(2), \dots, S(k)$ and look at $k + 1$. If $k + 1$ is prime, done. Split into the two possibilities: prime or not.
3. Otherwise factor it. $k + 1 = ab$ with $2 \le a, b \le k$. ‘Not prime’ means it has a factor other than 1 and itself, and both factors are then smaller than $k + 1$.
4. Use the strong hypothesis on BOTH factors. $a$ and $b$ are each a prime or a product of primes, so $ab$ is a product of primes. $a$ and $b$ can be anywhere between 2 and $k$, not just $k$. That is why ordinary induction is not enough here.

Answer. By strong induction, every $n \ge 2$ is a product of primes (a prime counts as a product of one prime). $\blacksquare$ Uniqueness of the factorisation is harder; it is in 0.5.

Solution.

1. Say what is to be shown. $S(n)$: $n = 3a + 5b$ for some integers $a, b \ge 0$. ‘Paid with coins’ means a count of each coin, and counts cannot be negative.
2. Choose the step first, to see how many base cases we need. To reach $k + 1$ we add one 3-rupee coin to a payment of $k + 1 - 3 = k - 2$. The step reaches back 3 places, so we may need 3 base cases. The step comes first so that it tells us how many bases to check.
3. Base cases. $8 = 3 + 5$, $9 = 3 \cdot 3$, $10 = 5 \cdot 2$. Three consecutive values, because the step reaches back 3.
4. Strong step. Let $k + 1 \ge 11$ and assume $S(8), \dots, S(k)$. Since $k + 1 \ge 11$, we have $k - 2 \ge 8$, so $S(k-2)$ holds: $k - 2 = 3a + 5b$. The hypothesis for $k - 2$ is available only because strong induction lets us use ALL earlier cases, not just $S(k)$. We need $k - 2 \ge 8$ to be inside the range of the claim.
5. Add the coin. $k + 1 = (k - 2) + 3 = 3(a + 1) + 5b$, with $a + 1, b \ge 0$. This is the required form.

Answer. Every $n \ge 8$ can be paid. $\blacksquare$ (Only the amounts $1, 2, 4, 7$ cannot be paid, which is why the claim starts at 8. With 4-rupee and 5-rupee coins the step reaches back 4 places, so it needs four base cases, $12, 13, 14, 15$. That is one of the problems below.)

Solution.

1. Assume the claim fails somewhere. Let $F$ be the set of integers $n \ge 1$ with $n \ge 2^n$. Suppose $F$ is not empty. This is a proof by contradiction. The set $F$ collects all the counterexamples.
2. Take the smallest counterexample. By well-ordering, $F$ has a smallest element $m$. Now we have one specific counterexample, and everything below $m$ is known to be fine.
3. Rule out $m = 1$. $1 < 2 = 2^1$, so $1 \notin F$. Hence $m \ge 2$ and $m - 1 \ge 1$. We want to use the case $m - 1$, so it must be a positive integer.
4. Use minimality. $m - 1 < m$, so $m - 1 \notin F$. That is, $m - 1 < 2^{m-1}$. $m$ is the smallest element of $F$, so nothing smaller is in $F$.
5. Double it. Since both sides are integers, $m - 1 < 2^{m-1}$ gives $m \le 2^{m-1}$, so $2^m = 2 \cdot 2^{m-1} \ge 2m$. Between integers, ‘less than’ lets us add 1 to the left side. Then double both sides.
6. Reach the contradiction. $2m \ge m + 1 > m$ because $m \ge 1$, so $2^m > m$, which says $m \notin F$. We assumed $m \in F$, that is $m \ge 2^m$.

Answer. $F$ must be empty, so $n < 2^n$ for every $n \ge 1$. $\blacksquare$

Solution.

1. Read the statement. “Infinitely many” is a negation: “not finitely many”. Statements that are themselves negations are natural for contradiction.
2. Assume the negation. Suppose the only primes are $p_1, \dots, p_m$. Contradiction gives us a concrete finite list to work with.
3. Build a new number. $N = p_1 p_2 \cdots p_m + 1$. Each $p_i$ divides the product, so dividing $N$ by $p_i$ leaves remainder 1.
4. Use the factorisation result. $N \ge 2$, so $N$ has a prime factor $p$ (previous example). Every integer at least 2 is a product of primes.
5. Derive the contradiction. $p$ must be some $p_i$, but no $p_i$ divides $N$. Remainder 1, not 0.

Answer. No finite list contains every prime. $\blacksquare$ (This is Euclid’s idea. He wrote it as “any finite list of primes is missing one” and did not use contradiction; the version above is the modern retelling. The list is not empty because 2 is a prime.)