Massachusetts Institute of Technology Handout ?? 6.042J/18.062J: Mathematics for Computer Science October 24, 2000 Professors Nancy Lynch and Srinivas Devadas

Problem Set 7

Due: 2:35pm in lecture, Tuesday, October 31, 2000.

Be sure to indicate your TA’s name clearly on the solutions your turn in.

—————————————————————————–

Self-study Read: Rosen Sections 4.1, 4.2, and 4.3 Self-study problems (not to be handed in):

—————————————————————————–

Reading: Lecture notes; Rosen 4.1, 4.2, and 4.3

Policy on collaboration If you collaborated with someone on the problem sets, you should mention their names on top of the problem set. If you did not collaborate with anyone, you should explicitly say so. As a reminder, the write-up of your solutions should be entirely your own.

Problem 1 Find closed-form solutions to the following homogenous linear recurrences.

(a) x_{n} = 5x_{n−1} − 6x_{n−2} (x_{0} = 0, x_{1} = 1)

The characteristic equation is r^{2} − 5r + 6 = 0. The roots can be found with the quadratic formula:

r_{1} = 2
r_{2} = 3

This implies a solution of the form

x_{n} = A2^{n} + B3^{n}.

Substituting the initial conditions into this general form gives a system of linear equations:

0 = A + B
1 = 2A + 3B

The solution to this system is A = −1 and B = 1. Therefore, the final solution to the recurrence is

x_{n} = 3^{n} − 2^{n}.

(b) x_{n} = 5x_{n−1} − 8x_{n−2} + 4x_{n−3} (x_{0} = 1, x_{1} = 2, x_{2} = 3)

The characteristic equation is r^{3} − 5r^{2} + 8r − 4 = 0. Solving a cubic equation can be messy process, but in this case the roots are easy to find:

r_{1} = 2
r_{2} = 2
r_{3} = 1

The general form of the solution is therefore

x_{n} = A2^{n} + Bn2^{n} + C.

Substituting the initial conditions into this general form gives a system of linear equations.

1 = A + C
2 = 2A + 2B + C
3 = 4A + 8B + C

The solution to this linear system is A = 2, B = −\frac{1}{2}, and C = −1. The complete solution to the recurrence is therefore

x_{n} = 2^{n+1} − n2^{n−1} − 1.

Problem 2 Find closed-form solutions to the following inhomogenous linear recurrences.

(a) (Fibonacci Plus) x_{n} = x_{n−1} + x_{n−2} + 1 (x_{0} = 0, x_{1} = 1)

First, we find the general solution to the homogenous recurrence. The characteristic equation is r^{2} − r − 1 = 0. The roots of this equation are:

r_{1} = \frac{1 + \sqrt{5}}{2}
r_{2} = \frac{1 − \sqrt{5}}{2}

Therefore, the solution to the homogenous recurrence is of the form

x_{n} = A (\frac{1 + \sqrt{5}}{2})^{n} + B (\frac{1 − \sqrt{5}}{2})^{n} .

Next, we need a particular solution to the inhomogenous recurrence. Since the inhomogenous term is constant, we guess a linear solution.

an + b = a(n − 1) + b + a(n − 2) + b + 1
= 2an − 3a + 2b + 1
0 = an − 3a + b + 1

This equation holds if we set a = 0 and b = −1. Therefore, the inhomogeous recurrence has the simple particular solution x_{n} = −1. The complete solution to the recurrence is the homogenous solution plus the particular solution:

x_{n} = A (\frac{1 + \sqrt{5}}{2})^{n} + B (\frac{1 − \sqrt{5}}{2})^{n} − 1

All that remains is to find the constants A and B. Substituting the initial conditions gives a system of linear equations.

0 = A + B − 1
1 = A (\frac{1 + \sqrt{5}}{2}) + B (\frac{1 − \sqrt{5}}{2}) − 1

The solution to this linear system is:

A = \frac{5 + 3\sqrt{5}}{10}
B = \frac{5 − 3\sqrt{5}}{10}

Therefore, the complete solution to the recurrence is

x_{n} = (\frac{5 + 3\sqrt{5}}{10}) · (\frac{1 + \sqrt{5}}{2})^{n} + (\frac{5 − 3\sqrt{5}}{10}) · (\frac{1 − \sqrt{5}}{2})^{n} − 1.

(b) x_{n} = 3x_{n−1} − 2x_{n−2} + n (x_{0} = 0, x_{1} = 1)

First, we find the general solution to the homogenous recurrence. The characteristic equation is r^{2} − 3r + 2 = 0. The roots of this equation are r_{1} = 1 and r_{2} = 2. Therefore, the general solution to the homogenous recurrence is

x_{n} = A + B2^{n}.

Now we must find a particular solution to the recurrence, ignoring the boundary conditions. Since the inhomogenous term is linear, we guess a solution that is quadratic:

an^{2} + bn + c = 3(a(n − 1)^{2} + b(n − 1) + c) − 2(a(n − 2)^{2} + b(n − 2) + c) + n
= an^{2} + 2an − 5a + bn + b + c + n
0 = 2an − 5a + b + n

This equation is solved by setting a = −\frac{1}{2} and b = −\frac{5}{2}. Apparently, any value of c gives a valid particular solution; for simplicity, we choose c = 0. Therefore, the particular solution is:

x_{n} = −\frac{1}{2}n^{2} − \frac{5}{2}n

The complete solution to the recurrence is the homogenous solution plus the particular solution:

x_{n} = A + B2^{n} − \frac{1}{2}n^{2} − \frac{5}{2}n

Substituting the initial conditions gives a system of linear equations:

0 = A + B
1 = A + 2B − 3

The solution to this linear system is A = −4 and B = 4. Therefore, the complete solution to the recurrence is

x_{n} = 2^{n+2} − \frac{1}{2}n^{2} − \frac{5}{2}n − 4.

Problem 3 The 6.042 staff recently received the following email.

From: grzzwk@xoros19.gammaquad.plnt
To: 6042-staff@theory.lcs.mit.edu
Subject: Pset 5 issue
Thank you for contributing the MergeSortX19 algorithm to our
``intellectually challenged'' society.  My, my-- we feel mentally
bloated by this sudden infusion of technological wizardry!
As a token of thanks, we launched a Doritofier missile on a straight
line toward Earth.  Suppose that p(t) denotes the distance between
Xoros 19 and the Doritofier after t days of flight.  At the moment of

launch, the Doritofier was here on Xoros 19, and so p(0) = 0.  After a
single day, the Doritofier had already traveled 100 units toward
Earth, so p(1) = 100.  In general, the position of the missle is given
by the following recurrence:
       p(t+1) = 1.99 * p(t) - p(t-1)
Earth happens to be 1010 units from Xoros 19.  Gotta run!  Seeya!
/Grzzwk

Find a closed-form solution to the recurrence for the distance between Xoros 19 and the Doritofier after t days of flight.

Let c = 1.99. The characteristic equation of Grzzwk’s recurrence is then r^{2} − cr + 1 = 0. The roots of this equation are:

r_{1} = \frac{c + \sqrt{c^{2} − 4}}{2}
r_{2} = \frac{c − \sqrt{c^{2} − 4}}{2}

Therefore, the general solution to the recurrence is:

p(t) = A (\frac{c + \sqrt{c^{2} − 4}}{2})^{t} + B (\frac{c − \sqrt{c^{2} − 4}}{2})^{t}

Subtituting the initial conditions into this general form gives a system of linear equations.

0 = A + B
100 = A (\frac{c + \sqrt{c^{2} − 4}}{2}) + B (\frac{c − \sqrt{c^{2} − 4}}{2})

The solution to this linear system is

A = \frac{100}{\sqrt{c^{2} − 4}}
B = −\frac{100}{\sqrt{c^{2} − 4}}

Therefore, the complete solution to the recurrence is

p(t) = \frac{100}{\sqrt{c^{2} − 4}} · ((\frac{c + \sqrt{c^{2} − 4}}{2})^{t} − (\frac{c − \sqrt{c^{2} − 4}}{2})^{t})

where c = 1.99. Note that \sqrt{c^{2} − 4} is imaginary.

Problem 4 For each of the functions below, determine whether the function is injective, whether it is surjective, and whether it is bijective. No proofs are required.

(a) The function f : ℝ ↦ ℝ defined by f(x) = e^{x}

The function is injective because e^{x} = e^{y} if and only if x = y. The function is not surjective, because e^{x} never takes on non-positive values. The function is not bijective, because it is not surjective.

(b) The function f : ℝ ↦ ℝ^{+} defined by f(x) = e^{x}. (Here ℝ^{+} denotes the set of positive real numbers.)

The function is injective as before, but is now also surjective because for every y ∈ ℝ^{+}, there exists an x (namely x = ln y) such that y = e^{x}. Therefore, the function is bijective.

(c) The function f : ℝ ↦ ℝ defined by (x + 1)/(x^{2} + 1)

The function is not injective, because f(0) = f(1) = 1. The function is not surjective, because the function never takes on large positive or negative values. The function is not bijective because it is neither injective nor surjective.

(d) The function f : ℝ ↦ ℝ defined by

f(x) = \{ \begin{matrix}1/x & for x ≠ 0 \\ 0 & for x = 0. \end{matrix}

The function is injective, because f(x) = f(y) if and only if x = y. The function is surjective, because for all y ∈ ℝ, there exists an x (namely x = 1/y or x = 0) such that f(x) = y. Therefore, the function is also bijective.

Problem 5 Multiple linear recurrences On a certain far away island, all men are either blond or brown-haired. Studies show that each man has four sons. Every blond father has exactly three blond sons, while every brown-haired man has exactly two brown-haired sons.

(a) Let a_{n} and b_{n} denote the number of blond and brown-haired men, respectively, in the nth generation. Write a system of recurrences for a_{n} and b_{n}.

\begin{aligned}a_{n} & = 3a_{n−1} + 2b_{n−1}, \\ b_{n} & = a_{n−1} + 2b_{n−1}. \end{aligned}

(b) For which values of c ≠ 0 and d will we have a solution of the form a_{n} = c^{n}, b_{n} = dc^{n}?

Assume a_{n} = c^{n} and b_{n} = dc^{n} for some c ≠ 0 and d. Let’s substitute this into the system of recurrences. We will obtain the equations

c^{n} = 3c^{n−1} + 2dc^{n−1},
dc^{n} = c^{n−1} + 2dc^{n−1}.

Dividing out c^{n−1} (which is allowed, since c ≠ 0), we obtain

\begin{aligned}c & = 3 + 2d, \\ dc & = 1 + 2d. \end{aligned}  (1)

Multiplying both sides of the first equation by d and subtracting the second equation, we obtain

0 = 3d + 2d^{2} − 1 − 2d = 2d^{2} + d − 1.

Solving the quadratic equation, we obtain d ∈ \{−1, \frac{1}{2}\}. Substituting into (1), we obtain the solutions

c = 1, d = −1;
c = 4, d = \frac{1}{2}.

(c) Show that there exist values for c_{1}, c_{2}, d_{1}, and d_{2} such that

\begin{aligned}a_{n} & = xc_{1}^{n} + yc_{2}^{n}, \\ b_{n} & = xd_{1}c_{1}^{n} + yd_{2}c_{2}^{n}, \end{aligned}

is a solution for all x and y.

Let c_{1} = 1, d_{1} = −1, c_{2} = 4, d_{2} = \frac{1}{2} (i.e., the two pairs of c and d that were obtained in part (a)). From part (a) we know that a_{n} = c_{i}^{n}, b_{n} = d_{i}c_{i}^{n} is a solution to the recurrences, for each i ∈ {1, 2}. It is easy to verify that a constant multiple of a solution is a solution, and that a sum of two solutions is a solution.

(d) Suppose in the first generation there were ten blond and twenty brown-haired men on the island. How many of each group will there be in the nth generation?

We have a_{1} = 10, b_{1} = 20. Let’s find x and y such that a solution in the form of part (d) would satisfy these initial conditions. We have

10 = x · 1^{1} + y · 4^{1},
20 = x · (−1) · 1^{1} + y · \frac{1}{2} · 4^{1},

which can be rewritten as

10 = x + 4y,
20 = −x + 2y.

This gives x = −10 and y = 5.

Thus the solution is

a_{n} = −10 + 5 · 4^{n},
b_{n} = 10 + \frac{5}{2} · 4^{n}.

Problem 6

(a) Theory Pig has often complained that the name “Pigeonhole Principle” is verbose and awkward. He proposes the more concise term “Pig Principle” for the same idea. Recently, he devised a couple problems involving this idea in order to promote his terminology.

Suppose that m pigs are lined up, and each pig is given one or more tasty treats. Prove that there is always a set of pigs that are consecutive in the lineup and that all together receive a number of treats that is a multiple of m.

For example, suppose that there are m = 5 pigs, and that they receive 1, 6, 2, 7, and 9 treats respectively. Then the claim holds in this case, because the second, third, and fourth pigs received 6 + 2 + 7 = 15 treats altogether, and 15 is a multiple of 5.

Let P_{i} be the total number of treats given out to the first i pigs. There are two cases. In the first case, suppose that at least one of P_{1}, P_{2}, …, P_{m} is congruent to 0 modulo m. In particular, suppose that P_{j} is congruent to 0 modulo m. This implies that the number of treats received by the first j pigs is a multiple of m, and so the claim holds. In the second case, suppose that none of P_{1}, P_{2}, …, P_{m} is congruent to 0 modulo m. Then each of the m terms P_{1}, P_{2}, …, P_{m} is congruent to one of the m − 1 values 1, 2, …, m − 1 modulo m. By the Pig Principle, there are at least two terms P_{j} and P_{k} that are congruent to the same value modulo m. Thus pigs j + 1, j + 2, …, k received a total of P_{k} − P_{j} treats, which is a multiple of m.

(b) A lattice point is a point in a coordinate plane for which both coordinates are integers. Prove that no matter what five lattice points might be chosen in the plane at least one of the segments that joins two of the chosen points must pass through some lattice point in the plane.

To show that one of the line segments connecting five lattice points must pass through some lattice point in the coordinate plane, note that there four ”parity” classes for the coordinates of a lattice point: odd, odd; odd, even; even, odd; and even, even. On the pigeonhole principle some two of the five lattice points, say (x_{1}, y_{1}) and (x_{2}, y_{2}) must belong to the same class. This implies that x_{1} + x_{2} and y_{1} + y_{2} are both even numbers, making the midpoint of the segment joining the points, namely [(x_{1} + x_{2})/2, (y_{1} + y_{2})/2], a lattice point.