Introduction to Algorithms - A Creative Approach: Chapter 2

Exercise 2.1

Prove xn−ynx^n - y^n is divisible by x−yx-y for all natural numbers x,y,x≠yx, y, x \neq y and nn.

Proof: The proof is by induction on nn.

Induction Hypothesis: xk−ykx^k - y^k is divisible by x−yx - y for all natural numbers x,y,x≠yx,y,x \neq y and all k<nk < n.

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

xn+1−yn+1 x^{n+1} - y^{n+1} x(xn−yn)+y(xn−yn)+xyn−yxn x(x^n - y^n) + y(x^n - y^n) + xy^n - yx^n x(xn−yn)+y(xn−yn)+xy(xn−1−yn−1) x(x^n - y^n) + y(x^n - y^n) + xy(x^{n-1} - y^{n-1})

All terms are divisible by x−yx - y by the induction hypothesis, therefore the expression is divisible by x−yx - 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 nn, given in its decimal representation, is congruent to k mod 3k \ \mathrm{mod}\ 3 if and only if the sum of its digits is congruent to k mod 3k \ \mathrm{mod}\ 3.

Proof: The claim is easily verified for small numbers.

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

  1. The last digit of n−1n-1 is not 9. Then both nn and the sum of the digits of nn are incremented by 1 and the relation holds.
  2. The last digit of n−1n-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 mod 39 \ \mathrm{mod}\ 3 and 0 mod 30 \ \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>1n > 1,

1n+1+1n+2+⋯+12n<1324 \frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n} < \frac{13}{24}

Proof: The proof is by induction on nn.

Induction Hypothesis: The theorem is true for all kk such that k<nk < n.

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

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

1k+2+1k+3+⋯+12k+12k+1+12k+2 \frac{1}{k+2} + \frac{1}{k+3} + \cdots + \frac{1}{2k} + \frac{1}{2k+1} + \frac{1}{2k+2} 1k+1+1k+2+1k+3+⋯+12k+12k+1+12k+2−1k+1 \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 1k+1+1k+2+1k+3+⋯+12k>1324\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,

12k+1+12k+2−1k+1≥0 \frac{1}{2k+1} + \frac{1}{2k+2} - \frac{1}{k+1} \geq 0 12k+1+12k+2−22k+2≥0 \frac{1}{2k+1} + \frac{1}{2k+2} - \frac{2}{2k+2} \geq 0 12k+1≥12k+2 \frac{1}{2k+1} \geq \frac{1}{2k+2} 2k+2≥2k+1 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>1n>1

1+12+13+⋯+1n=km 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \frac{k}{m}

where kk is an odd number and mm is an even number.

Proof: The proof is by strong induction on nn

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

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

For the odd denominators, we have: ac=1+13+15+⋯+1p\frac{a}{c} = 1 + \frac{1}{3} + \frac{1}{5} + \cdots + \frac{1}{p}, where pp is the largest odd number less than or equal to tt.

We know cc must be odd, because all of the denominators are odd. We can ignore aa.

For the even denominators, we have: bd=12+14+⋯+1q\frac{b}{d} = \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{q}, where qq is the largest even number less than or equal to nn.

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

1+12+13+⋯+1n=ac+bd 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \frac{a}{c} + \frac{b}{d} =ad+bccd = \frac{ad + bc}{cd}

We know dd is even, so adad is even and both bb and cc are odd, so bcbc is odd. Hence the numerator is odd. dd is even, so the denominator is even.

Exercise 2.19

Prove that the regions formed by nn 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 nn.

Base Case: One circle only needs one color.

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

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

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

  1. The n−1n-1 circle doesn’t intersect any other circle. Then we can simply pick our favorite color and call it good.
  2. The n−1n-1 circle intersects some circles. We can color the n−1n-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.
Published on by .