Long(er)-Form Mathematics

Proofs: Hints and Solutions

Try plugging in actual values for $x$ and $y$ and see what happens.

A similar problem was discussed in Chapter 1. How did we prove it that time?

The answer is yes, although the proof is a little tricky. Try to find an explicit way to do it.

This problem is not too different than the other chessboard problems we have discussed. Do you see why?

Choosing $n+1$ things, and wanting two of something in the end… that sounds like the pigeonhole principle! What are your boxes and what are your objects?

Choosing $n+1$ things, and wanting two of something in the end… that sounds like the pigeonhole principle! What are your boxes and what are your objects?

You want a hint for “your own words”?? Bro….

In the end, you are looking for two things with some property (relatively prime). That sounds like the simple form of the pigeonhole principle. What are your boxes and what are your objects?

Look through the chapter and see if you can find a similar problem that we solved. How did we do it there?

Look through the chapter and see if you can find a similar problem that we solved. How did we do it there?

We defined a counterexample on page 11.

The problem asks “how many” of something are needed until something else is guaranteed… that sounds a lot like the pigeonhole principle.

Use the definitions of even and odd. We did several similar problems in Chapter 2.

Part (a) looks more complicated, but stick to your fundamentals. Start by using the definition of an odd number.

You can use the definition of an odd or even number on both $m$ and $n!$.

Try a proof by cases.

As general advice: Whenever possible, start by writing down some examples of specific numbers (in this case, for $m$ and $n$) and see what patterns you can see.

For part (d), perhaps there is a theorem (or a Lemma….) from this chapter that could help?

Try a proof by cases.

If the first two are not even, what would that tell us about the third one?

For part (a), perhaps a proof by cases would be beneficial. For part (b), given some multiple of 4, like $4k$, try to determine which $n$ works, in terms of $k$.

If the problem asked for $a=17$ and $m=3$, then the quotient would be 5 and the remainder would be 2. (Writing it as “$a=mq+r$”, we would have $17 = 3\cdot 5+2$.)

Remember that if you are dividing by aa, then the remainder $r$ would have to have this property: $0 \leq r \leq a$.

This is the same thing as asking for the value of $r$ (where $0 \leq 28$) for which $3^{302} \equiv r$ (mod 28). Now, recall that exponentiation is the same as repeated multiplication, and we proved a proposition this chapter that related multiplication and mods.

We proved something similar in Chapter 2. How did we prove it then?

We proved a lemma this chapter that might be helpful.

Consider a proof by cases.

One proof uses the definition of modular congruence. Another proof is super short and uses a proposition from Chapter 2 .

This is not a hint, but just want to emphasize that this is a pretty neat result! I had looked at many Pythagorean triples in my life before ever realizing this.

Take a moment to marvel at the miracle that this is true. To prove it: If $k$ divides $21n+4$ and $14n+3$, then it must divide $2(21n+4)$ and $3(14n+3)$. Multiply these out and see if you notice something interesting.

Consider the integers $(n+1)!+2$, $(n+1)!+3$, $(n+1)!+4$, … , $(n+1)!  +(n+1)$.

Not a hint, but according to my brother you can see the personalities of each of his cats based on how many of these pictures they were willing to appear in.

For part (b), turn every term into a fraction. For example, $\pi$ can be written like $\frac{2\pi}{2}$. For part (d), find formulas for the numerator and denominator separately.

If you’re confused about how to think about sets inside of sets, go back to the box-inside-a-box metaphor on the second page of this chapter.

For part (a), there are 8 subsets.

By “a familiar set” I mean a set that you have seen and has a name, like $\emptyset$ or $\mathbb{Z}$ or $\mathbb{R}$ or some set like that.

Perhaps it will be helpful by doing an explicit example. Pick actual sets, like you could let $A = \{1,2\}$.

Since the equation looks very similar to the equation in Theorem 3.16, perhaps its proof will be very similar to the proof of Theorem 3.16.

Begin your proof by choosing an $x \in \mathcal{P}(A) \cup \mathcal{P}(B)$. The apply the definitions of union, and eventually aim to show that $x \in \mathcal{P}(A \cup B)$.

$A \subsetneq B$ if $A$ has an element that $B$ does not have.

As with all set equalities, one way to prove each of these is to choose an element from the left set and show it is also in the right set, and then vice versa.

For some, drawing a Venn diagram could help you figure out why it is or is not true. For others, you could gain intuition by picking specific sets. For example, let $A=\{1,2\}$, and let the others be other small sets. Or perhaps you could let these all be large sets that you’re familiar with, like $\mathbb{N}$ or $\mathbb{Z}$ or $\emptyset$. Just remember: If statement is false, then a single example can be a counterexample; but if a statement is true, then a single example will not be proof.

If you draw the Venn diagram first, then it might help you come up with the specific sets for your counterexample.

Not really a hint, but after you find an example, draw a Venn diagram with three circles, for sets $A$, $B$ and $C$ and add in the elements from your example. Look at your diagram to see pictorially why your example worked.

It’s possible to prove all of these in the condensed way shown on page 115.

What this is saying is that two sets are equal. And to prove $A=B$, one way is to prove $A \subseteq B$ and $B \subseteq A$.

One element from $A \times \mathcal{P}(A)$ is $(a,\{b\})$.

For part (a), both answers are an interval. Will they be open intervals or closed intervals? Which intervals?

In your Induction Step, use the definition of divisibility.

Use the fact that if $a<b$, then $a+c < b+c$.

Check if the inequality is true for $n=1$, $n=2$, $n=3$, and so on. For which $n$ do you conjecture it will hold for?

Recall that $3^{k+1} = 3 \cdot 3^k$.

It is not true that every 2 people have the same name, so the error must be in moving from $n=1$ to $n=2$. Where does the argument fail with those cases?

The Fake Proof does prove something, but what is it that it proves?

Plug in numbers for $a$ and $b$ and see! Can you find natural numbers $a$ and $b$ for which $3a+7b=1$? What about equal to 2? To 3? To 4? When is the last time that it fails? While doing this, remember that $a$ and $b$ must be natural numbers; that is, they must equal positive integers.

One formula is $n(n+1)$. This can be found by working from Proposition 4.2.

$m+(m+1)+\cdots+n=(1+2+\cdots+n)−(1+2+\cdots+(m−1)).$

Every subset of ${1,2,\dots,k+1}$ either contains the element $k+1$ or does not. Two options.

Use Induction. The inductive hypothesis will be $a_1^2 + \dots + a_k^2 = b^2$. then consider $a_1^2 + \dots + a_k^2 + b^2$. This sum is not guaranteed to be a perfect square, but a related sum is. It uses one more idea: That 3^2 + 4^2 = 5^2$. 

This is true for $n=0$ but false for $n=1$ , so the reasoning must fail somewhere when moving from $n=0$ to $n=1$.

For part (a), use induction and Lemma 2.17. For part (b), use part (a).

Review how we proved Proposition 4.5. A similar idea will work here.

Try to use strong induction with 4 base cases.

Try strong induction.

For each implication, think about what the contrapositive tells you.

Recall Definition 5.1, which says that statements must have a truth value. If they are not true or false, then they are not statements.

For each, there is more than one right is answer.

Page 211 might be helpful.

Page 211 might be helpful.

If you know that $x$ and $y$  are numbers, what is a number (in terms of $x$ and $y$) that is between these two numbers? Will that number be rational if $x$ and $y$ are?

What does it mean for something to be vacuously true?

You will need to use DeMorgan’s logic law (Theorem 5.9).

After using the contrapositive, it will turn into a standard problem from Chapter 2.

After using the contrapositive, it will turn into a standard problem from Chapter 2.

When you take the contrapositive in part (a), you will have to negate “$m$is even or $n$ is odd.” When doing so, remember to use DeMorgan’s logic law. (Theorem 5.9). Likewise in parts (b) and (c).

When you take the contrapositive in part (a), you will need to use DeMorgan’s logic law. (Theorem 5.9).

Oftentimes when proving an “if and only if” result, one direction you will prove with a direct proof, while the other direction you will prove by using the contrapositive.

If two things are equal, then they must share all of the same properties. So if you can identify any property that one side has, that the other side does not, then that is a contradiction.

Use the definitions of even/odd integers.

If a set does not equal the empty set, that means it contains at least one element. Choose such an element and look for the contradiction.

Recall that two sets $X$ and $Y$ are disjoint if they share no elements. In other words, if $X\cap Y=\emptyset$ . By saying that $A\setminus B$ , $B\setminus A$ and $A\cap B$ are “pairwise disjoint,” we mean that $A\setminus B$ and $B]setminus A$ are disjoint, and also that $A\setminus B$ and $A\cap B$ are disjoint, and also that $B\setminus A$ and $A\cap B$ are disjoint.

For part (b), use part (a). For part (e), if you assume that $\sqrt{2} + \sqrt{5} = a/b$ for some integers $a$ and $b$, then square both sides and use part (d).

There are many different ways to prove this. Once you’ve found one way, look for a couple more!

By the logic form of DeMorgan’s law, you should be assuming for a contradiction that $a$ and $b$ are odd.

At some point, perhaps at the very beginning or the very end, you might use the fact that $(x-y)^2 \geq 0$.

At some point, perhaps at the very beginning or the very end, you might use the fact that $(x-y)^2 \geq 0$.

There are several ways to prove this. You might make use of mods. You might think about the cases where $n$ is even or $n$ is odd. You might use rules of divisibility or something else.

Assume there was an n and m where $n^2+n+1=m^2$ . Does this mean $m>n$ or $n>m$? Figure out which. Then, by thinking about $(n+1)^2$ , what else can you deduce?

Suppose they did intersect. Then do some algebra and see what that would imply.

Contrapositive and/or contradiction will be useful for at least one of the two directions. Also, think about what it means for two numbers to be of the same distance from xx—one must be some distance dd to the left of xx, while the other must be distance dd to the right. What would that mean about xx, relative these two?

For part (a), the proof I have in mind does not use contradiction, but it does use the theorem from Chapter 7 that there are infinitely many primes. Let $N=n!$ and let $p$ be a prime larger than $N$ . Consider now the sequence

\[p , p+N , p+2N , p+3N , … , p+(n−1)N.\]

A function is only defined when you have identified its domain and codomain.

The outputs are all natural numbers. The range are all the numbers that can actually be hit. For example, 12 is in the range because $(2,1)$ is in the codomain and $f(2,1)=2^2 3^1=12.$

To be a function, there are existence and uniqueness criteria: every input has to have an output, and has to have only one output. Does this rule for $f$ satisfy those?

To prove that a function f is injective, set $f(x)=f(y)$ and do algebra to try to deduce that $x=y$ . To prove that f is surjective, pick any b in the codomain and try to find an a in the domain for which $f(a)=b$ . To prove $f$ is not injective, try to find two elements in the domain that map to the same number (eg., maybe $f(2)=f(5)$). To prove $f$ is not surjective, try to find an element of the codomain that nothing in the domain maps to (eg., maybe 7 is in the codomain, and $f(x)\neq 7$ . for all $x$ from the domain).

I suggest doing lots of examples before starting. This is a tricky function with a tricky domain and rule; only with many examples will it make sense.

For both directions, I suggest using the contrapositive. Assuming that $f$ is non-surjective or not-injective is a more concrete position to start from, since it gives you a specific element or pair of elements with a special property.

Functions on ordered pairs are always a little confusing. To get a sense of what’s going on, do some examples first. Plug in, say, $(1,2)$ into $g$  and then plug the answer into $f$.

For examples, it is useful to think carefully about the functions’ domains, codomains, and ranges. It’s possible to pick functions with big domains, like $\mathbb{R}$ , but it is also possible to pick domains and codomains with just a few elements.

It’s possible that your answer from Exercise 8.17 will work for this problem, too.

One way to disprove it would be to find a counterexample. That is, specific functions for which the equation does not hold.

Draw a few examples of increasing functions. In calculus you learned that discontinuities happen at specific points, and that discontinuities can look like holes in your graph, like jumps in the graph, or like neither, because the function is going haywire at the point. Keep these in mind as you draw out some examples.

If you know a function’s domain and codomain, then a function is entirely determined by where each element in the domain is mapped to; different mappings produce different functions. Given an element of the domain, $a$, how many different options are there for $f(a)$?

Try starting simple. Maybe let $A={1,2,3}$ and let $B={a,b,c}$. Draw out three dots for $A$ and three dots for $B$ , and start drawing functions from $A$ to $B$ and see if you can find an example which doesn’t satisfy the equation. Once you get one example, think about what property of your example allowed for it to work.

Exercise 9.4

For part (a), there are two partitions. For part (b), there are 5 partitions.

To be reflexive, you need every element to be related to itself. However, remember that symmetry and transitivity are of the “If, then” variety. Symmetry says that if you have $a\sim b$ , then you must also have $b\sim a$ . But without the “if,” you don’t need the “then.” For example, to be symmetric, you don’t need to have $a\sim b$ and $b\sim a$ for all $a$ and $b$ . However, if you do have $a\sim b$ , then you also need $b\sim a$ . Alternatively, you can think about it as preventing symmetry. A relation is not symmetric if there exists some $a\sim b$ while also $b$≁$a$ . But as long as that does not happen, the relation is symmetric.

To be reflexive, you need every element to be related to itself. However, remember that symmetry and transitivity are of the “If, then” variety. Symmetry says that if you have $a\sim b$ , then you must also have $b\sim a$ . But without the “if,” you don’t need the “then.” For example, to be symmetric, you don’t need to have $a\sim b$ and $b\sim a$ for all $a$ and $b$ . However, if you do have $a\sim b$ , then you also need $b\sim a$ . Alternatively, you can think about it as preventing symmetry. A relation is not symmetric if there exists some $a\sim b$ while also $b$≁$a$ . But as long as that does not happen, the relation is symmetric.

To be reflexive, you need every element to be related to itself. However, remember that symmetry and transitivity are of the “If, then” variety. Symmetry says that if you have $a\sim b$ , then you must also have $b\sim a$ . But without the “if,” you don’t need the “then.” For example, to be symmetric, you don’t need to have $a\sim b$ and $b\sim a$ for all $a$ and $b$ . However, if you do have $a\sim b$ , then you also need $b\sim a$ . Alternatively, you can think about it as preventing symmetry. A relation is not symmetric if there exists some $a\sim b$ while also $b$≁$a$ . But as long as that does not happen, the relation is symmetric.

To be reflexive, you need every element to be related to itself. However, remember that symmetry and transitivity are of the “If, then” variety. Symmetry says that if you have $a\sim b$ , then you must also have $b\sim a$ . But without the “if,” you don’t need the “then.” For example, to be symmetric, you don’t need to have $a\sim b$ and $b\sim a$ for all $a$ and $b$ . However, if you do have $a\sim b$ , then you also need $b\sim a$ . Alternatively, you can think about it as preventing symmetry. A relation is not symmetric if there exists some $a\sim b$ while also $b$≁$a$ . But as long as that does not happen, the relation is symmetric.

To give an example, it is sufficient to simply write out all pairs that are related. You don’t need a “rule” that determines the relation like in the four rules in Exercise 9.3.. You can just write out the related elements like we did in Exercise 9.9.

To prove that a relation is an equivalence relation, you must show that it is reflexive, symmetric and transitive. Do each part separately like we did in Example 9.7.

To prove that a relation is an equivalence relation, you must show that it is reflexive, symmetric and transitive. Do each part separately like we did in Example 9.7.

The point of this problem is to practice using the reflexive, symmetric and transitive properties. What relations must be there because ~ is reflexive? Given the relations you just wrote down and the three given in the problem, what other relations must hold because ~ is symmetric? Likewise for transitive.

One of these is an equivalence relation and the other one is not.

Yes, ~ will be an equivalence relation. Prove this by showing it is reflexive, symmetric and transitive. To do this, use the fact that $\tilde_1$ and $\tilde_2$ are reflexive, symmetric and transitive.

Notice that the gap between consecutive elements is 3, and that’s the case for all three sets.

One way to think about the equivalence relation’s rule is as a function. That is, there is some function $f$ for which $a\tilde b$ if and only if $f(a)=f(b)$. What function works for these equivalence classes?

For the example where it is an equivalence relation, think of a very simple function.

Remember that functions have an existence and uniqueness criterion than relations do not have.