Problem Set 5

Due Friday, February 14 at 1:00 PM Pacific

Solutions are available!

🔑 Solutions

This problem set – the last one purely on discrete mathematics – is designed as a cumulative review of the topics we’ve covered so far and a proving ground to try out your newfound skills with mathematical induction. The problems here span all sorts of topics and we hope that it serves as a fitting coda to our whirlwind tour of discrete math!

We recommend that you read the Guide to Induction before starting this problem set. It contains a lot of useful advice about how to approach problems inductively, how to structure inductive proofs, and how to not fall into common inductive traps. Additionally, before submitting, be sure to read over the Induction Proofwriting Checklist for a list of specific things to watch for in your solutions before submitting.

As a note on this problem set – normally, you're welcome to use any proof technique you'd like to prove results in this course. On this problem set, we've specifically asked on some problems that you prove a result inductively. For those problems, you should prove those results using induction or complete induction, even if there is another way to prove the result. (If you'd like to use induction in conjunction with other techniques like proof by contradiction or proof by contrapositive, that's perfectly fine.)

Good luck, and have fun!

Starter Files

This problem set does not have a coding component.

If you would like to type your solutions in $\LaTeX$, you may want to download this template file where you can place your answers:

🖋 PS5 $\LaTeX$ Template

General Advice

First, read through the index of problems below to get an idea of time management for this assignment.
Next, glance through all the questions before you start working. This not only ensures you won't be caught off guard as you reach later problems, but also gives your brain a chance to start working on some of these as a background process while you do other things.
If you get stuck, consider moving on to another problem for a while! Changing things up is a great way to get out of a rut, make new connections between concepts, and spark creative insights!
If you realize you don't have the requisite knowledge to complete a problem, take a step back from it and review the relevant lecture materials. Skipping lecture and trying to extract the relevant tidbits for each problem will lead to a more frustrating experience than engaging fully with a lecture and approaching the problem sets afterward.

Timeline

This pset has six required problems (all of which are written / manually graded). Because all the questions are of similar flavors (analyzing and writing inductive proofs!), we are listing them all on a single page.

We recommend the following timeline for completing questions:

Q1 and Q2 by Sunday evening
Q3 by Tuesday evening
Q4 by Wednesday evening
Q5 by Thursday evening
Q6 could fit in on Tuesday, Wednesday, or Thursday

Of course, we recommend reading through the entire problem set ASAP so you have a strong idea of how much time the problems will take and so your brain can start working on them as a background process. :)

Problem One: Induction Proof Critiques

Below are a collection of proofs by induction. For each proof, do the following:

Critique the proofwriting style in regards to the Induction Proofwriting Checklist and Guide to Induction.
Identify any logic errors in the execution of the proofs and explain why they are logic errors.
Determine whether the "theorem" being proved is actually true. If it's true, just tell us that it's true. If it's false, give a counterexample.

You do not need to rewrite these proofs – just give us your feedback on the items we mentioned by filling in this table:

Checklist Item	Violation?	If Yes, say where the error is and briefly explain what exactly went wrong.
Make $P(n)$ a predicate, not a number or function.	Yes/No
Watch your variable scoping in $P(n)\text.$	Yes/No
"Build up" if $P(n)$ is existentially quantified; "build down" if $P(n)$ is universally-quantified.	Yes/No
Choose the simplest base cases possible, and avoid redundant base cases.	Yes/No
Are there any logic errors? If so, where, and why are they logic errors?
Is the overall theorem true? If so, just say so. If not, give a counterexample.

Critique the following proof about sums of natural numbers.

Theorem: The sum of the first $n$ natural numbers is $\frac{n(n - 1)}{2}$.

Proof: Let $P(n) = \frac{n(n - 1)}{2}$. We will prove by induction on $n$ that $P(n)$ holds for all $n \in \naturals$, from which theorem follows.

As our base cases, we prove $P(0)$ and $P(1)$. First we’ll prove $P(0)$, that the sum of the first zero natural numbers is $\frac{0(0 - 1)}{2}$. The sum of no numbers is the empty sum $(0)\text,$ and we see that $\frac{0(0 - 1)}{2} = 0$, so $P(0)$ is true. Next, we’ll prove $P(1)$. The sum of the first natural number is $0$ (since $0$ is the smallest natural number), and we note that $\frac{1(1 - 1)}{2} = 0$, so $P(1)$ is true.

For our inductive step, assume for all natural numbers $k$ that $P(k)$ is true. This means
\[0 + 1 + 2 + \dots + (k - 1) \quad = \quad \frac{k(k - 1)}{2}\text.\]
We will prove $P(k+1)$, that the sum of the first $k+1$ natural numbers is equal to $\frac{(k + 1)k}{2}$. Starting with the sum of the first $k+1$ natural numbers, we see that
\[\begin{array}{lcl} 0 + 1 + 2 + \dots + (k - 1) + k & = & \frac{(k+1)k}{2} \\ 0 + 1 + 2 + \dots + (k - 1) & = & \frac{(k + 1)k}{2} - k \\ 0 + 1 + 2 + \dots + (k - 1) & = & \frac{(k + 1)k}{2} - \frac{2k}{2}\\ 0 + 1 + 2 + \dots + (k - 1) & = & \frac{(k + 1 - 2)k}{2} \\ 0 + 1 + 2 + \dots + (k - 1) & = & \frac{k(k - 1)}{2} \text. \end{array}\]
We've reached our inductive hypothesis, so the equation is true. Thus $P(k+1)$ holds, completing the induction. $\qed$

Critique the following proof about directed graphs.

Theorem: No directed graphs have any cycles.

Proof: Let $P(n)$ be the statement “for any $n \in \naturals$, no directed graph with $n$ nodes contains a cycle.” We will prove by induction that $P(n)$ holds for all $n \in \naturals$, from which the theorem follows.

As a base case, we prove $P(0)$, that no directed graphs with $0$ nodes contain a cycle. To see this, consider any directed graph $G$ with no nodes. Since $G$ has no nodes, it has no closed walks, since all closed walks contain at least one node. Therefore, $G$ has no cycles, as required.

For our inductive step, assume for some arbitrary $k \in \naturals$ that P(k) is true and no directed graph with $k$ nodes has any cycles. We will prove that $P(k+1)$ is true, namely, that no directed graphs with $k+1$ nodes have any cycles.

Consider a directed graph $G$ with $k$ nodes. By our inductive hypothesis, we know that $G$ has no cycles. Now, consider the graph $G'$ formed by adding a new node $v$ to $G$, then adding edges from $v$ to each node in $G$. We claim that this directed graph has no cycles. To see this, note that any cycle in $G'$ must involve $v$, since $G$ has no cycles on its own. But this is impossible, since any walk that leaves $v$ can never return to it and therefore can't be a closed walk. Therefore, $G'$ has no cycles, so $P(k+1)$ holds, completing the induction. $\qed$

Problem Two: Recurrence Relations

A recurrence relation is a way of defining an infinitely long sequence (usually, a sequence of numbers). A recurrence relation specifies the value of the first term or terms of the sequence, then defines the remaining entries from the previous terms. For example, here’s a simple recurrence relation:

\[a_0 = 1 \qquad a_{n+1} = 2a_n\]

The first terms of this sequence are given as follows:

$a_0 = 1$, since that’s what the first rule says.
$a_1 = 2$, since the second rule says that $a_1 = 2a_0 = 2 \cdot 1 = 2\text.$
$a_2 = 4$, since the second rule says that $a_2 = 2a_1 = 2 \cdot 2 = 4\text.$
$a_3 = 8$, since the second rule says that $a_3 = 2a_2 = 2 \cdot 4 = 8\text.$

Extending further, this sequence starts off with the numbers

\[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, \dots,\]

which all happen to be powers of two. It turns out that this isn't a coincidence – this recurrence relation perfectly describes the powers of two.

Fill in the blanks below to complete the proof by induction.

Theorem: For all natural numbers $n$, we have $a_n = 2^n$.

Proof: Let $P(n)$ be the statement "$a_n = 2^n$." We will prove by induction that $P(n)$ holds for all $n \in \naturals$, from which the theorem follows.

As our base case, we prove $P(\blank)$, that $\blank$. To see this, $\blank$.

For our inductive step, assume for some arbitrary $k \in \naturals$ that $P(k)$ is true, meaning that $\blank$. We need to show $P(\blank)$, meaning that $\blank$. To see this, note that

\[\begin{aligned} a_{k+1} &= \blank \\ &= \blank && \text{(by our IH)} \\ &= \blank \text. \end{aligned}\]

Therefore, we see that $\blank$, so $P(\blank)$ is true, completing the induction. $\qed$

The relative sizes of the blanks here do not necessarily indicate how much you need to write in each spot.

In case you’re wondering what you’re asked to prove here, you can think of this recurrence relation as a mathematical way of writing out this recursive function:

int a(int n) {
    if (n == 0) return 1;
    return 2 * a(n - 1);
}

For any $n \in \naturals$, you can compute a(n) by just running this code, and after doing some computation it will return the value of $a_n$. What we’re asking you to do is the mathematical equivalent of showing that the value returned by a(n) is always $2^n$. While it might help to think about things in terms of this analogy, your proof should not reference this code and should just use the definitions given in the problem statement.

Taking a recurrence relation like the relation $a_n$ here and finding a simple, non-recursive expression for it is called solving the recurrence. It's common in theoretical CS to need to solve recurrences. For example, when determining the efficiency of a recursive algorithm, you might first start by writing a recurrence relation for its runtime, then solve the recurrence to get a simpler, direct way of calculating its efficiency. Take CS161 to learn how to do this!

Problem Three: Square Triangular Numbers

As a refresher, a natural number $n$ is called a square number when there is a natural number $k$ such that $n = k^2\text.$ Similarly, a natural number $n$ is a triangular number when there is a natural number $k$ such that $n = \frac{k(k+1)}{2}\text.$

Some numbers are both square and triangular. For example, 36 is both square $(36 = 6^2)$ and triangular $(36 = \frac{8(8+1)}{2})\text.$ You can see this visually below; each figure is made of 36 squares.

There are infinitely many numbers that are both square and triangular. To see this, consider the following recurrence relation:

\[a_0 = 1 \qquad a_{n+1} = 4a_n \cdot (8a_n + 1)\text.\]

Prove by induction that $a_n$ is both square and triangular for all natural numbers $n\text.$

Problem Four: Presenting Presenters Presents

There is a conference for people who host events (emcees). Each emcee arrives with gifts for up to three other emcees. To avoid ruining surprises, the event organizer sets the following rule: no emcee is allowed to stay at the same hotel as a emcee they will give a gift to. The question then arises - how many hotels are necessary to house the emcees?

You might think that if there's a big group of emcees (say, 100 or so) and each one arrives with three gifts that you would need a lot of hotels to house everyone. But that's actually not the case. It turns out you never need more than seven hotels to hold everyone.

We’re going to ask you to prove this using a proof by induction with this predicate $P(n)$:

$P(n)$ is the predicate “for any group of $n$ emcees, each of whom has gifts for up to three other emcees, there is a way to house the emcees in seven hotels so that no emcee stays at a hotel with a emcee they have a gift for”

Before proceeding, let’s confirm you see the general structure of the proof.

Is $P(n)$ a universally-quantified statement or an existentially-quantified statement? Based on that, will you “induct up,” or will you “induct down?”

There are multiple quantifiers in $P(n)$. We care about the first one.

Prove by induction that $P(n)$ is true for all $n \in \naturals$.

It might be helpful to think about the emcee who receives the fewest number of gifts.

Problem Five: Regular Graphs

A graph $G = (V, E)$ is called $d$-regular if every node in $G$ has degree exactly $d$. (As a reminder, the degree of a node $v$ is the number of edges that have $v$ as an endpoint, or, equivalently, the number of nodes that $v$ is adjacent to.)

For example, here's a 3-regular graph with 6 nodes and a 4-regular graph with 7 nodes:

Prove by induction that for all natural numbers $n$ there exists an $n$-regular graph containing exactly $2^n$ nodes.

Is this a problem where you'll "induct up," or a problem where you'll "induct down?"

As a hint, moving from $2^k$ to $2^{k+1}$ doubles the number of nodes in the graph, and moving from $2^{k+1}$ to $2^k$ halves the number of nodes in the graph. If you think this is an "induct up" problem, try finding a natural way to "double" a graph. If you think this is an "induct down" problem, try finding a natural way to "halve" a graph.

Regular graphs often make appearances in combinatorics and theoretical computer science. Graphs with the specific property you're exploring in this problem - where there are a huge number of nodes of modest degree - have applications in parallel computing, network design, and error-correcting codes. Take CS144 (Computer Networks), CS149 (Parallel Computing) or CS250 (Algebraic Error-Correcting Codes) to learn more!

Problem Six: It’ll All Even Out

Our very first proof by induction was the proof that for any natural number $n$, we have that

\[2^0 + 2^1 + 2^2 + \dots + 2^{n-1} = 2^n - 1\text.\]

This result is still true for the case where $n = 0$, since in that case the sum on the left-hand side of the equation is the empty sum of zero numbers, which is by definition equal to zero. It’s also true for the case where $n = 1$; in that case, the sum on the left-hand side of the equality just has a single term in it ($2^0$) and the right-hand side has the same value.

Below is a proof by complete induction of an incorrect statement about sums of real numbers.

⚠ (Incorrect!) ⚠ Theorem: Let $x_1, x_2, x_3, \dots, x_n$ be any $n$ real numbers. Then $x_1 + x_2 + \dots + x_n$ is even.

⚠ (Incorrect!) ⚠ Proof: Let $P(n)$ be the statement “for any $n$ real numbers $x_1, x_2, \dots, x_n\text,$ the sum $x_1 + x_2 + \dots + x_n$ is even.” We will prove by complete induction that $P(n)$ holds for all $n \in \naturals$, from which the theorem follows.

As a base case, we prove $P(0)$, that the sum of any $0$ real numbers is even. The sum of any zero numbers is the empty sum and is by definition equal to $0$, which is even. Thus $P(0)$ holds.

For our inductive step, assume for some arbitrary $k \in \naturals$ that $P(0), \dots, \text{ and } P(k)$ are true. We will prove that $P(k+1)$ is true. To do so, let $x_1, x_2, \dots, x_k, \text{ and } x_{k+1}$ be arbitrary real numbers and consider the sum

\[x_1 + x_2 + \dots + x_k + x_{k+1}\text.\]

We can group the first $k$ terms and the last term independently to see that

\[x_1 + x_2 + \dots + x_k + x_{k+1} = (x_1 + x_2 + \dots + x_k) + x_{k+1}\text.\]

Now, consider the sum $x_1 + x_2 + \dots + x_k$ of the first $k$ terms. This is the sum of $k$ real numbers, so by our inductive hypothesis that $P(k)$ is true we know that this sum must be even. Similarly, consider the sum $x_{k+1}$ consisting of just the single term $x_{k+1}$. By our inductive hypothesis that $P(1)$ is true, we know that this sum must be even.

Overall, we have shown that $x_1 + x_2 + \dots + x_k + x_{k+1}$ can be written as the sum of two even numbers (namely, $x_1 + x_2 + \dots + x_k$ and $x_{k+1}$), so $x_1 + x_2 + \dots + x_k + x_{k+1}$ is even. Thus $P(k+1)$ is true, completing the induction. $\qed$

Of course, this theorem isn’t true, so the proof must be wrong. But what specifically did it do wrong?

The proof defines a predicate $P(n)$, then uses complete induction to prove $P(n)$ holds for all $n \in \naturals$. Is $P(n)$ actually a predicate? Does $P(n)$ meet all requirements in the Induction Proofwriting Checklist? Is it actually the case that, if $P(n)$ is true for all $n \in \naturals$, then the theorem in question is true? If any of your answers are “no,” explain why, pointing out, specifically, what the proof does wrong.

Is $P(0)$ true? Is the base case of this proof written correctly? If so, just say “yes, it’s correct.” If not, point out a specific claim it makes that’s incorrect and explain why it’s incorrect.

We aren’t looking for “sins of omission” here in the sense of “the proof should have also done $X$ in addition to what it already did.” Rather, we’re looking for “sins of commission” in sense of “the proof does $X$, and $X$ is incorrect.”

Is $P(1)$ true? Is the inductive step of this proof written correctly? If so, just say “yes, it’s correct.” If not, point out a specific claim it makes that’s incorrect and explain why it’s incorrect.

Optional Fun Problem: Egyptian Fractions

Leonardo Fibonacci, an eleventh-century Italian mathematician, is credited with introducing Hindu-Arabic numerals (the number system we use today) to Europe in his book Liber Abaci. The book Liber Abaci is also the source of the Fibonacci sequence (a sequence that begins 0, 1 and where each successive term is the sum of the two previous terms).

Relevant for this problem, Liber Abaci also described a method of writing out fractions called Egyptian fractions, which has been employed since ancient times; the Rhind Mathematical Papyrus, composed about 3,500 years ago in Thebes, includes several tables of fractions written out this way.

An Egyptian fraction is a sum of distinct fractions whose numerators are all 1 (these fractions are called unit fractions). For example, here are some sample Egyptian fraction representations:

\[\begin{array}{c} \frac{2}{3} = \frac{1}{2} + \frac{1}{6} \\ \frac{2}{15} = \frac{1}{10} + \frac{1}{30} \\ \frac{7}{15} = \frac{1}{3} + \frac{1}{8} + \frac{1}{120} \\ \frac{2}{85} = \frac{1}{51} + \frac{1}{255} \end{array}\]

Egyptian fractions are useful for divvying up objects fairly. For example, suppose you have two cakes to distribute to fifteen people – that is, everyone should get a $\frac{2}{15}$ fraction of those cakes. Begin by slicing each cake into tenths and giving each person one ($\frac{1}{10}$). Now, take the remaining tenths you haven’t distributed and cut them into thirds, giving thirtieths of the original cake. Each person then takes one of those ($\frac{1}{30}$). Because $\frac{1}{10} + \frac{1}{30} = \frac{2}{15}$, everyone gets their fair share. Pretty cool, isn’t it?

It's not immediately obvious that every fraction between 0 and 1 can be written this way, but, surprisingly, that is indeed the case. One way of finding an Egyptian fraction representation of a number is to use a greedy algorithm that works by finding the largest unit fraction at any point that can be subtracted out from the rational number. For example, to compute an Egyptian fraction representation for $\frac{42}{137}$, we would start off by noting that $\frac{1}{4}$ is the largest unit fraction less than $\frac{42}{137}$. We then say that

\[\frac{42}{137} = \frac{1}{4} + (\frac{42}{137} - \frac{1}{4}) = \frac{1}{4} + \frac{31}{548} \text.\]

We then repeat this process by finding the largest unit fraction less than $\frac{31}{548}$ and subtracting it out. This number is $\frac{1}{18}$, so we get

\[\frac{42}{137} = \frac{1}{4} + \frac{1}{18} + (\frac{31}{548} - \frac{1}{18}) = \frac{1}{4} + \frac{1}{18} + \frac{5}{4,932} \text.\]

The largest unit fraction we can subtract from $\frac{5}{4932}$ is $\frac{1}{987}$:

\[\frac{42}{137} = \frac{1}{4} + \frac{1}{18} + \frac{1}{987} (\frac{5}{4,932} - \frac{1}{987}) = \frac{1}{4} + \frac{1}{18} + \frac{1}{987} + \frac{1}{1,622,628} \text.\]

And at this point we're done, because the leftover fraction is itself a unit fraction.

Prove that the greedy algorithm for Egyptian fractions always terminates for any rational number $r$ in the range $0 \lt r \lt 1$ and always produces a valid Egyptian fraction. (A rational number is a real number that can be written as $r = \frac{p}{q}$ for some integers $p$ and $q$ where $q \ne 0$.) That is, the sum of the unit fractions should be the original number, there should only be finitely many fractions, and no unit fraction should be repeated. This shows that every rational number in the range $0 \lt r \lt 1$ has at least one Egyptian fraction representation. ```