Massachusetts Institute of Technology Handout 38 6.042J/18.062J: Mathematics for Computer Science October 23, 1998 Professors Nancy Lynch and Srinivas Devadas

Problem Set 6 Solutions

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}) · B (\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

(a) 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.

(b) The characteristic equation approach gives a solution to this recurrence involving complex numbers. This makes evalutation awkward. Give a closed-form solution that does not involve complex numbers. DeMoivre’s Identity may be helpful:

(cos θ + i sin θ)^{n} = cos nθ + i sin nθ

We start with the solution obtained previously.

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

Note that

\frac{c + \sqrt{c^{2} − 4}}{2} = \frac{c}{2} + i · \sqrt{1 − (\frac{c}{2})^{2}}
= cos θ + i sin θ

where θ = arccos \frac{c}{2}. With this substitution, we can eliminate complex numbers from the solution.

p(t) = \frac{100}{\sqrt{c^{2} − 4}} · ((cos θ + i sin θ)^{t} − (cos θ − i sin θ)^{t})
= \frac{100}{\sqrt{c^{2} − 4}} · ((cos tθ + i sin tθ) − (cos tθ − i sin tθ))
= \frac{100}{\sqrt{c^{2} − 4}} · (2i sin tθ)
= \frac{100}{\sqrt{1 − (\frac{c}{2})^{2}}} · (sin tθ)
= \frac{100 sin tθ}{sin θ}

The final solution is

p(t) = \frac{100 sin tθ}{sin θ}

where θ = arccos(\frac{1.99}{2}).

(c) Does the Doritofier missle hit earth? The solution indicates that the path of the Doritofier is a sine wave with amplitude

\frac{100}{sin θ} = \frac{100}{sin arccos (\frac{c}{2})}
= \frac{100}{\sqrt{1 − (\frac{c}{2})^{2}}}
= \frac{100}{\sqrt{1 − (\frac{1.99}{2})^{2}}}
= 1001.253 …

Since Earth is 1010 units from Xoros 19, we’re safe. On the other hand, since the path of the missle is a sine wave, it will be returning to Xorox 19 presently...