# Introduction to Algorithms - A Creative Approach: Chapter 2

## Exercise 2.1

Prove $x^n - y^n$ is divisible by $x-y$ for all natural numbers $x, y, x \neq y$ and $n$.

**Proof**: The proof is by induction on $n$.

**Induction Hypothesis**: $x^k - y^k$ is divisible by $x - y$ for all natural numbers $x,y,x \neq y$ and all $k < n$.

The case for $n=0$ and $n=1$ is trivial. Assume the claim is true for $n$ and consider $n+1$.

$x^{n+1} - y^{n+1}$ $x(x^n - y^n) + y(x^n - y^n) + xy^n - yx^n$ $x(x^n - y^n) + y(x^n - y^n) + xy(x^{n-1} - y^{n-1})$

All terms are divisible by $x - y$ by the induction hypothesis, therefore the expression is divisible by $x - y$.

## Exercise 2.9

Prove by induction that a number, given in its decimal representation, is divisible by 3 if and only if the sum of its digits is divisible by 3.

**Theorem**: A number $n$, given in its decimal representation, is congruent to $k
\ \mathrm{mod}\ 3$ if and only if the sum of its digits is congruent to $k \ \mathrm{mod}\ 3$.

**Proof**: The claim is easily verified for small numbers.

Assume the theorem is true for $n-1$ and consider $n$. The difference between the decimal representation of $n$ and $n-1$ is only in the last digit, unless the last digit of $n-1$ is 9. Consider the following two cases:

- The last digit of $n-1$ is not 9. Then both $n$ and the sum of the digits of $n$ are incremented by 1 and the relation holds.
- The last digit of $n-1$ is 9. Then we change the 9 to 0 and add 1 to the second to last digit. Changing the 9 to a 0 doesn’t change the relation, as both $9 \ \mathrm{mod}\ 3$ and $0 \ \mathrm{mod}\ 3$ is 0. Adding 1 to the second to last digit increases both the sum of the digits by 1 and the number by 1 and the relation holds. If the second to last digit is also a 9, we repeat this case.

## Exercise 2.12

Prove, that for all $n > 1$,

$\frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n} < \frac{13}{24}$

**Proof**: The proof is by induction on $n$.

**Induction Hypothesis**: The theorem is true for all $k$ such that $k < n$.

The theorem is true for $k = 2$ because $\frac{1}{3} + \frac{1}{4} = \frac{14}{24} > \frac{13}{24}$

Consider $k+1$. We’ll rearrange the left side of the equation.

$\frac{1}{k+2} + \frac{1}{k+3} + \cdots + \frac{1}{2k} + \frac{1}{2k+1} + \frac{1}{2k+2}$ $\frac{1}{k+1} + \frac{1}{k+2} + \frac{1}{k+3} + \cdots + \frac{1}{2k} + \frac{1}{2k+1} + \frac{1}{2k+2} - \frac{1}{k+1}$

We know by the induction hypothesis that $\frac{1}{k+1} + \frac{1}{k+2} + \frac{1}{k+3} + \cdots + \frac{1}{2k} > \frac{13}{24}$. We only need to show that the remaining part of the equation is greater than or equal to zero. That is,

$\frac{1}{2k+1} + \frac{1}{2k+2} - \frac{1}{k+1} \geq 0$ $\frac{1}{2k+1} + \frac{1}{2k+2} - \frac{2}{2k+2} \geq 0$ $\frac{1}{2k+1} \geq \frac{1}{2k+2}$ $2k+2 \geq 2k+1$

## Exercise 2.13

This problem was marked as “especially challenging”, a sentiment that I agree with. I used the friendly folks at Math.StackExchange to solve this problem. Proving the sum of fractions has an odd numerator and an even denominator.

Prove that, for all $n>1$

$1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \frac{k}{m}$

where $k$ is an odd number and $m$ is an even number.

**Proof**: The proof is by strong induction on $n$

Base Case: $1 + \frac{1}{2} = \frac{3}{2}$

Assume the theorem is true for all $t$ such $t < n$. We first break the equation apart by grouping fractions with even denominators and those with odd denominators.

For the odd denominators, we have: $\frac{a}{c} = 1 + \frac{1}{3} + \frac{1}{5} + \cdots + \frac{1}{p}$, where $p$ is the largest odd number less than or equal to $t$.

We know $c$ must be odd, because all of the denominators are odd. We can ignore $a$.

For the even denominators, we have: $\frac{b}{d} = \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{q}$, where $q$ is the largest even number less than or equal to $n$.

We can modify $\frac{b}{d}$ to fit induction hypothesis by factoring out $\frac{1}{2}$ from each element, $\frac{b}{d} = \frac{1}{2}(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{\frac{q}{2}})$. By the induction hypothesis, $b$ is odd and $d$ is even.

$1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \frac{a}{c} + \frac{b}{d}$ $= \frac{ad + bc}{cd}$

We know $d$ is even, so $ad$ is even and both $b$ and $c$ are odd, so $bc$ is odd. Hence the numerator is odd. $d$ is even, so the denominator is even.

## Exercise 2.19

Prove that the regions formed by $n$ circles in the plan can be colored with two colors such that any neighboring regions are colored differently.

**Proof**: The proof is by induction on $n$.

Base Case: One circle only needs one color.

Assume the theorem is true for $n - 1$ and consider $n$.

Let’s first remove the $n-1$ circle for a bit. Now we have a total of $n-1$ circles, with the $n^{\mathrm{th}}$ circle taking the place of the $n-1$ circle. By the inductive hypothesis, we have a valid coloring.

Now, lets consider what happens when we re-add the $n-1$ circle. There are three cases:

- The $n-1$ circle doesn’t intersect any other circle. Then we can simply pick our favorite color and call it good.
- The $n-1$ circle intersects some circles. We can color the $n-1$ circle by
inverting colors based on the number of overlapping circles. If the number
of overlaps is even, then we invert that region. If the number of overlaps
is odd, we leave the color the same. A region with an even number of
overlaps cannot be adjacent to a region with an odd number of overlaps.
**I can’t figure out how to explain why this is true**.