0Introduction and Preliminaries 0.2Mathematical Statements
Exercises
0.2.18.
Hint.
Try an example. What if \(P(x)\) was the predicate, “\(x\) is prime”? What if it was “if \(x\) is divisible by 4, then it is even”? Of course examples are not enough to prove something in general, but that is entirely the point of this question.
It might help to think about what the union \(A_2
\cup A_3\) is first. Then think about what numbers are not in that union. What will happen when you also include \(A_5\text{?}\)
You could consider cases. For example, any number of the form ODD-ODD-EVEN will have an even sum. Alternatively, how many three digit numbers have the sum of their digits even if the first two digits are 54? What if the first two digits are 19?
For a simpler example, there are 4 divisors of \(6 = 2\cdot 3\text{.}\) They are \(1 = 2^0\cdot 3^0\text{,}\)\(2 = 2^1\cdot 3^0\text{,}\)\(3 = 2^0\cdot 3^1\) and \(6 = 2^1\cdot 3^1\text{.}\)
If you pick any three points, you can get a triangle, unless those three points are all on the \(x\)-axis or on the \(y\)-axis. There are other ways to start this as well, and any correct method should give the same answer.
For the lattice paths, think about what sort of paths \(2^n\) would count. Not all the paths will end at the same point, but you could describe the set of end points as a line.
Try an example: when you draw the 4th line, it will cross three other lines, so will be divided into four segments, two of which are infinite. Each segment will divide a previous region into two.
Consider three cases: the last digit is a 0, a 1, or a 2. Two of these should be easy to count, but strings ending in 0 cannot be proceeded by a 2, so require a little more work.
There is only one way to tile a \(2 \times 1\) board, and two ways to tile a \(2\times 2\) board (you can orient the dominoes in two ways). In general, consider the two ways the domino covering the top left corner could be oriented.
For the inductive step, you can assume you have a strictly increasing sequence up to \(a_k\) where \(a_k \lt 100\text{.}\) Now you just need to find the next term \(a_{k+1}\) so that \(a_{k} \lt a_{k+1} \lt 100\text{.}\) What should \(a_{k+1}\) be?
For the inductive case, you will need to show that \((k+1)^2 + (k+1)\) is even. Factor this out and locate the part of it that is \(k^2 + k\text{.}\) What have you assumed about that quantity?
This is similar to Exercise 2.5.15, although there you were showing that a sequence had all its terms less than some value, and here you are showing that the sum is less than some value. But the partial sums forms a sequence, so this is actually very similar.
As with the previous question, we will want to subtract something from \(n\) in the inductive step. There we subtracted the largest power of 2 less than \(n\text{.}\) So what should you subtract here?
Note, you will still need to take care here that the sum you get from the inductive hypothesis, together with the number you subtracted will be a sum of distinct Fibonacci numbers. In fact, you could prove that the Fibonacci numbers in the sum are non-consecutive!
The question you need to answer to complete the inductive step is, how many new handshakes take place when a person \(k+1\) enters the room. Why does adding this give you the correct formula?
You will need to use strong induction. For the inductive case, try multiplying \(\left (x^k + \frac{1}{x^{k}}\right)\left(x+\frac{1}{x}\right)\) and collect which terms together are integers.
Here’s the idea: since every entry in Pascal’s Triangle is the sum of the two entries above it, we can get the \(k+1\)st row by adding up all the pairs of entry from the \(k\)th row. But doing this uses each entry on the \(k\)th row twice. Thus each time we drop to the next row, we double the total. Of course, row 0 has sum \(1 = 2^0\) (the base case). Now try to make this precise with a formal induction proof. You will use the fact that \({n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\) for the inductive case.
To see why this works, try it on a copy of Pascal’s triangle. We are adding up the entries along a diagonal, starting with the 1 on the left-hand side of the 4th row. Suppose we add up the first 5 entries on this diagonal. The claim is that the sum is the entry below and to the left of the last of these 5 entries. Note that if this is true, and we instead add up the first 6 entries, we will need to add the entry one spot to the right of the previous sum. But these two together give the entry below them, which is below and left of the last of the 6 entries on the diagonal. If you follow that, you can see what is going on. But it is not a great proof. A formal induction proof is needed.
You are allowed to assume the base case. For the inductive case, group all but the last function together as one sum of functions, then apply the usual sum of derivatives rule, and then the inductive hypothesis.
You will need three base cases. This is a very good hint actually, as it suggests that to prove \(P(n)\) is true, you would want to use the fact that \(P(n-3)\) is true. So somehow you need to increase the number of squares by 3.
Careful to actually use induction here. The base case: \(2^2 = 4\text{.}\) The inductive case: assume \((2n)^2\) is divisible by 4 and consider \((2n+2)^2 = (2n)^2 + 4n + 4\text{.}\) This is divisible by 4 because \(4n +4\) clearly is, and by our inductive hypothesis, so is \((2n)^2\text{.}\)
This is a straight forward induction proof. Note you will need to simplify \(\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3\) and get \(\left(\frac{(n+1)(n+2)}{2}\right)^2\text{.}\)
There are two base cases \(P(0)\) and \(P(1)\text{.}\) Then, for the inductive case, assume \(P(k)\) is true for all \(k \lt n\text{.}\) This allows you to assume \(a_{n-1} = 1\) and \(a_{n-2} = 1\text{.}\) Apply the recurrence relation.
You should write down three statements using the symbols \(P, Q, R, S\text{.}\) If Geoff is a truth-teller, then all three statements would be true. If he was a liar, then all three statements would be false. But in either case, we don’t yet know whether the four atomic statements are true or false, since he hasn’t said them by themselves.
Write down three statements, and then take the negation of each (since he is a liar). You should find that Tommy ate one item and drank one item. (\(Q\) is for cucumber sandwiches.)
For the second part, you can inductively assume that from the first \(n-2\) implications you can deduce \(P_1 \imp P_{n-1}\text{.}\) Then you are back in the case in part (a) again.
It might help to translate the statements into symbols and then use the formulaic rules to simplify negations (i.e., rules for quantifiers and De Morgan’s laws). After simplifying, you should get \(\forall x(\neg E(x) \wedge \neg O(x))\text{,}\) for the first one, for example. Then translate this back into English.
This is really an exercise in modifying the proof that \(\sqrt{2}\) is irrational. There you proved things were even; here they will be multiples of 3.
A proof by contradiction would be reasonable here, because then you get to assume that both \(a\)and\(b\) are odd. Deduce that \(c^2\) is even, and therefore a multiple of 4 (why? and why is that a contradiction?).
Consider the set of numbers of friends that everyone has. If everyone had a different number of friends, this set must contain 20 elements. Is that possible? Why not?
This feels like the pigeonhole principle, although a bit more complicated. At least, you could try to replicate the style of proof used by the pigeonhole principle. How would the episodes need to be spaced out so that no two of your sixty were exactly 4 apart?
The bipartite graph is a little tricky. You will definitely want a complete bipartite graph, but it could be \(K_{5,5}\) or maybe \(K_{1,9}\text{,}\) or …
You should be able to deduce everything directly from the definition. However, perhaps it would be helpful to know that the \(N\) stands for neighborhood.
Be careful to make sure the edges are not “directed.” In a graph, if \(a\) is adjacent to \(b\text{,}\) then \(b\) is adjacent to \(a\text{.}\) In the language of relations, we say that the edge relation is symmetric.
You might want to answer the questions for some specific values of \(n\) to get a feel for them, but your final answers should be in terms of \(n\text{.}\)
Examining the proof of Proposition 4.2.1 gives you most of what you need, but make sure to just give the relevant parts, and take care to not use proof by contradiction.
If \(e\) is the root, then \(b\) will have three children (\(a\text{,}\)\(c\text{,}\) and \(d\)), all of which will be siblings, and have \(b\) as their parent. \(a\) will not have any children.
Note that you cannot use the 4-color theorem, or Brooke’s theorem, or the clique number here. In fact, this graph, called the Grötzsch graph is the smallest graph with chromatic number 4 that does not contain any triangles.
You can color \(K_5\) in such a way that every vertex is adjacent to exactly two blue edges and two red edges. However, there is a graph with only 5 edges that will result in a vertex incident to three edges of the same color no matter how they are colored. What is it, and how can you generalize?
If you read off the names of the students in order, you would need to read each student’s name exactly once, and the last name would need to be of a student who was friends with the first. What sort of a cycle is this?
You might want to give the proof in two parts. First prove by induction that the cycle \(C_n\) has \(v=e\text{.}\) Then consider what happens if the graph is more than just the cycle.
