% Homework 6 solutions, CSCE 235, spring 2007
% Assigned 2 April 2007; due 9 April 2007

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=8.5truein
\pdfhorigin=1.5truein \pdfvorigin=1.25truein

\headline={\hfil}
\footline={\hfil Page~\folio\hfil}

\newcount\pno
\pno=0
\def\problem{\advance\pno by1 \noindent{\bf Problem~\the\pno.} }
\def\problemno#1. {\noindent{\bf Problem~\hbox{#1}.} }
\def\solution{\nobreak\medskip\noindent{\bf Solution.} }
\def\part#1{\medskip\indent\llap{#1\enspace}\ignorespaces}
\def\mathpart#1#2\par{{%
	\abovedisplayskip=-\ht\strutbox \advance\abovedisplayskip by-\dp\strutbox %
	\abovedisplayshortskip=-\ht\strutbox \advance\abovedisplayshortskip by-\dp\strutbox %
	\part{#1}#2\par}}

\def\implies{\;\Longrightarrow\;}
\def\N{\mathord{\bf N}}  \def\Z{\mathord{\bf Z}}
\def\Q{\mathord{\bf Q}}  \def\R{\mathord{\bf R}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}

\centerline{CSCE~235: Introduction to Discrete Structures}
\centerline{{\bf Homework assignment~6} (solutions)}
\centerline{Assigned Monday, April~2, 2007}
\centerline{Due Monday, April~9, 2007}

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (12~points) Let $a_n=2^n+5\cdot3^n$ for $n=0,1,2,\ldots$.
\smallskip
\item{(a)} Find $a_0$,~$a_1$, $a_2$, $a_3$, and~$a_4$.
\item{(b)} Show that $a_2=5a_1-6a_0$, $a_3=5a_2-6a_1$, and $a_4=5a_3-6a_2$.
\item{(c)} Show that $a_n=5a_{n-1}-6a_{n-2}$ for all integers~$n$ with $n\ge2$.

\solution
\mathpart{(a)}
$$\eqalign{
	a_0&=2^0+5\cdot3^0=6,\cr
	a_1&=2^1+5\cdot3^1=17,\cr
	a_2&=2^2+5\cdot3^2=49,\cr
	a_3&=2^3+5\cdot3^3=143,\cr
	a_4&=2^4+5\cdot3^4=421.\cr
}$$

\mathpart{(b)}
$$\eqalign{
	a_2&=49=5\cdot17-6\cdot6=5a_1-6a_0,\cr
	a_3&=143=5\cdot49-6\cdot17=5a_2-6a_1,\cr
	a_4&=421=5\cdot143-6\cdot49=5a_3-6a_2.\cr
}$$

\part{(c)} For $n\ge2$,
$$\eqalign{
	a_n&=2^n+5\cdot3^n\cr
	&=2\cdot2^{n-1}+5\cdot3\cdot3^{n-1}\cr
	&=(5-3)\cdot2^{n-1}+(25-10)\cdot3^{n-1}\cr
	&=5\cdot2^{n-1}+25\cdot3^{n-1}-3\cdot2^{n-1}-10\cdot3^{n-1}\cr
	&=5\cdot2^{n-1}+25\cdot3^{n-1}-3\cdot2\cdot2^{n-2}-10\cdot3\cdot3^{n-2}\cr
	&=5\cdot2^{n-1}+25\cdot3^{n-1}-6\cdot2^{n-2}-30\cdot3^{n-2}\cr
	&=5(2^{n-1}+5\cdot3^{n-1})-6(2^{n-2}+5\cdot3^{n-2})\cr
	&=5a_{n-1}-6a_{n-2}.\cr
}$$

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (16~points) Is the sequence~$\{a_n\}$ a solution of the recurrence
relation $a_n=8a_{n-1}-16a_{n-2}$ if
\smallskip
\hbox{
\hskip\parindent\vbox{
\hbox{\llap{(a)\enspace}\strut$a_n=0$?}
\hbox{\llap{(b)\enspace}$a_n=1$?}
\hbox{\llap{(c)\enspace}$a_n=2^n$?}
\hbox{\llap{(d)\enspace}$a_n=4^n$?}
}\hskip1truein\vbox{
\hbox{\llap{(e)\enspace}$a_n=n4^n$?}
\hbox{\llap{(f)\enspace}$a_n=2\cdot4^n+3n4^n$?}
\hbox{\llap{(g)\enspace}$a_n=(-4)^n$?}
\hbox{\llap{(h)\enspace}$a_n=n^24^n$?}
}}

\solution
\part{(a)} Yes; $a_n=0=8\cdot0-16\cdot0=8a_{n-1}-16a_{n-2}$.

\part{(b)} No; $a_n=1\not=8\cdot1-16\cdot1=8a_{n-1}-16a_{n-2}$.

\part{(c)} No; $a_n=2^n\not=0=8\cdot2^{n-1}-16\cdot2^{n-2}=8a_{n-1}-16a_{n-2}$.

\part{(d)} Yes; $a_n=4^n=2\cdot4^n-4^n=8\cdot4^{n-1}-16\cdot4^{n-2}=8a_{n-1}-16a_{n-2}$.

\part{(e)} Yes;
$$\eqalign{
	a_n&=n\cdot4^n\cr
	&=n(2\cdot4^n-4^n)-2\cdot4^n+2\cdot4^n\cr
	&=2\cdot4^n(n-1)-4^n(n-2)\cr
	&=8(n-1)\cdot4^{n-1}-16(n-2)\cdot4^{n-2}\cr
	&=8a_{n-1}-16a_{n-2}.\cr
}$$

\part{(f)} Yes;
$$\eqalign{
	a_n&=2\cdot4^n+3n\cdot4^n\cr
	&=4^n(2+3n)\cr
	&=4^n\left[4+6(n-1)-2-3(n-2)\right]\cr
	&=4\cdot4^n+6(n-1)\cdot4^n-2\cdot4^n-3(n-2)\cdot4^n\cr
	&=8\left[2\cdot4^{n-1}+3(n-1)\cdot4^{n-1}\right]
		-16\left[2\cdot4^{n-2}+3(n-2)\cdot4^{n-2}\right]\cr
	&=8a_{n-1}-16a_{n-2}.\cr
}$$

\part{(g)} No; for example,
$a_2=(-4)^2=16\not=-48=8(-4)-16\cdot1=8a_1-16a_0$.

\part{(h)} No; for example,
$a_2=2^2\cdot4^2=64\not=32=8\cdot4-16\cdot0=8a_1-16a_0$.

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (12~points) Assume that the population of the world in~2007 is
6.6~billion and that the population will grow at the constant rate of 1.14\%
each year.
\smallskip
\item{(a)} Set up a recurrence relation for the population of the world
$n$~years after~2007.
\item{(b)} Find an explicit formula for the population of the world $n$~years
after~2007.
\item{(c)} What will the population of the world be in~2027?
\item{(d)} When will the world population reach 10~billion?

\solution
\part{(a)} Let $P_n$ represent the world population $n$~years after~2007. Then
we have, for $n=1$,~2, 3, \dots,
$$P_n=1.0114P_{n-1}.$$

\mathpart{(b)} $$P_n=(6.6\times10^9)(1.0114)^n.$$

\mathpart{(c)} $$P_{20}=(6.6\times10^9)(1.0114)^{20}\approx\hbox{8.28 billion}.$$

\part{(d)} We find that
$$(6.6\times10^9)(1.0114)^{36.656\ldots}\approx\hbox{10 billion},$$
so the world population will reach 10~billion about 36.7~years after~2007. How
should this be interpreted? One possibility is to read ``after~2007'' as
``after January~1, 2007,'' in which case our answer is August~27, 2043. Another
way is to reason that the population in~2043 is just under 10~billion, and the
population in~2044 is just over 10~billion, so the actual date must be
somewhere between the ``census dates'' of 2043 and~2044.

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (12~points) A vending machine dispensing books of stamps accepts only
dollar coins, \$1~bills, and \$5~bills.
\smallskip
\item{(a)} Find a recurrence relation for the number of ways to deposit
$n$~dollars into the machine, where the order in which the coins and bills are
deposited matters.
\item{(b)} What are the initial conditions?
\item{(c)} How many ways are there to deposit \$10 for a book of stamps?

\solution
\part{(a)} Let $A_n$ represent the number of ways to deposit $n$~dollars into
the machine.

Suppose we wish to deposit $n$~dollars into the machine, where $n\ge5$. The
first piece of currency we deposit must be either a dollar coin, a \$1~bill, or
a \$5~bill. If we begin by depositing a dollar coin, then we have
$A_{n-1}$~ways to deposit the rest of the money. If instead we first deposit a
\$1~bill, then we also have $A_{n-1}$~ways to deposit the rest of the money.
Finally, if we start by depositing a \$5~bill, then we have $A_{n-5}$~ways to
deposit the rest of the money.

In total, then, the number of ways to deposit $n$~dollars into the machine is
$$A_n=A_{n-1}+A_{n-1}+A_{n-5}=2A_{n-1}+A_{n-5},$$
for $n=5$, 6, 7,~\dots.

\part{(b)} Our recurrence relation works only for $n\ge5$, and requires a
value for~$A_{n-5}$, so our initial conditions are
$$A_0=1,\qquad A_1=2,\qquad A_2=4,\qquad A_3=8,\qquad A_4=16.$$

\part{(c)} We use our recurrence relation and initial conditions to compute
$$\eqalign{
	A_5&=2A_4+A_0=2\cdot16+1=33,\cr
	A_6&=2A_5+A_1=2\cdot33+2=68,\cr
	A_7&=2A_6+A_2=2\cdot68+4=140,\cr
	A_8&=2A_7+A_3=2\cdot140+8=288,\cr
	A_9&=2A_8+A_4=2\cdot288+16=592,\cr
	A_{10}&=2A_9+A_5=2\cdot592+33=1217.\cr
}$$
So there are 1217~ways to deposit~\$10 into the machine.

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) Find the solution to the recurrence relation
$$a_n=7a_{n-1}-10a_{n-2}\qquad\hbox{for $n\ge2$,}$$
with initial conditions $a_0=2$ and $a_1=1$.

\solution The characteristic polynomial of this recurrence relation is
$r^2-7r+10$, which we notice factors as $(r-5)(r-2)$. Therefore, the roots of
this polynomial, i.e., the characteristic roots of the recurrence relation,
are $r=5$ and $r=2$. So the general solution to the recurrence relation is
$$a_n=\alpha_1\cdot5^n+\alpha_2\cdot2^n$$
for some constants $\alpha_1$ and~$\alpha_2$. The initial conditions give us
$$\eqalign{
	a_0&=2=\alpha_1\cdot5^0+\alpha_2\cdot2^0=\alpha_1+\alpha_2,\cr
	a_1&=1=\alpha_1\cdot5^1+\alpha_2\cdot2^1=5\alpha_1+2\alpha_2.\cr
}$$
Solving this system of linear equations yields
$$\alpha_1=-1,\qquad\alpha_2=3.$$
So the solution to this recurrence relation with these initial conditions is
$$a_n=-5^n+3\cdot2^n.$$

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) Find the solution to the recurrence relation
$$a_n=-6a_{n-1}-9a_{n-2}\qquad\hbox{for $n\ge2$,}$$
with initial conditions $a_0=3$ and $a_1=-3$.

\solution The characteristic polynomial of this recurrence relation is
$r^2+6r+9$, which factors as $(r+3)(r+3)$, so the characteristic root is
$r=-3$, with multiplicity~2. Thus the general solution to the recurrence relation
is
$$a_n=\alpha_1\cdot(-3)^n+\alpha_2\cdot n\cdot(-3)^n$$
for some constants $\alpha_1$ and~$\alpha_2$. The initial conditions give us
$$\eqalign{
	a_0&=3=\alpha_1(-3)^0+\alpha_2\cdot0\cdot(-3)^0=\alpha_1,\cr
	a_1&=-3=\alpha_1(-3)^1+\alpha_2\cdot1\cdot(-3)^1=-3\alpha_1-3\alpha_2,\cr
}$$
so $\alpha_1=3$ and $\alpha_2=-2$. Therefore the solution to this recurrence
relation under the given initial conditions is
$$a_n=3(-3)^n-2n(-3)^n.$$

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) Find the solution to the recurrence relation
$$a_n=2a_{n-1}+5a_{n-2}-6a_{n-3}\qquad\hbox{for $n\ge3$,}$$
with initial conditions $a_0=7$, $a_1=-4$, and $a_2=8$.
\smallskip
\noindent{\it Hint:\/} You will need to use Theorem~3 on page~465 of the
textbook.

\solution The characteristic polynomial is $r^3-2r^2-5r+6$, which factors as
$(r-3)(r-1)(r+2)$. Hence the characteristic roots are $r=3$, $r=1$, and $r=-2$,
and the general solution to the recurrence relation is
$$a_n=\alpha_1\cdot3^n+\alpha_2\cdot1^n+\alpha_3\cdot(-2)^n$$
for some constants $\alpha_1$,~$\alpha_2$, and~$\alpha_3$. The initial
conditions give us
$$\eqalign{
	a_0&=7=\alpha_1\cdot3^0+\alpha_2+\alpha_3\cdot(-2)^0=\alpha_1+\alpha_2+\alpha_3,\cr
	a_1&=-4=\alpha_1\cdot3^1+\alpha_2+\alpha_3\cdot(-2)^1=3\alpha_1+\alpha_2-2\alpha_3,\cr
	a_2&=8=\alpha_1\cdot3^2+\alpha_2+\alpha_3\cdot(-2)^2=9\alpha_1+\alpha_2+4\alpha_3.\cr
}$$
Solving this system of linear equations yields
$$\alpha_1=-1,\qquad\alpha_2=5,\qquad\alpha_3=3.$$
So the solution to this recurrence relation with the given initial conditions
is
$$a_n=-3^n+5+3\cdot(-2)^n.$$

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) The Lucas numbers satisfy the recurrence relation
$$L_n=L_{n-1}+L_{n-2}\qquad\hbox{for $n\ge2$,}$$
with the initial conditions $L_0=2$ and $L_1=1$. Find an explicit formula for
the Lucas numbers.

\solution The Lucas numbers satisfy the same recurrence relation as the
Fibonacci numbers. In class we showed that the general solution to this
recurrence relation is
$$L_n=\alpha_1\left(1+\sqrt5\over2\right)^n+\alpha_2\left(1-\sqrt5\over2\right)^n$$
for some constants $\alpha_1$ and~$\alpha_2$. Using the initial conditions
given, we get
$$\eqalign{
	L_0&=2=\alpha_1\left(1+\sqrt5\over2\right)^0+\alpha_2\left(1-\sqrt5\over2\right)^0=\alpha_1+\alpha_2,\cr
	L_1&=1=\alpha_1\left(1+\sqrt5\over2\right)^1+\alpha_2\left(1-\sqrt5\over2\right)^1=\left(1+\sqrt5\over2\right)\alpha_1+\left(1-\sqrt5\over2\right)\alpha_2.\cr
}$$
Solving this system of equations, we obtain
$$\alpha_1=1\qquad\hbox{and}\qquad\alpha_2=1.$$
So an explicit formula for the $n$th Lucas number is
$$L_n=\left(1+\sqrt5\over2\right)^n+\left(1-\sqrt5\over2\right)^n.$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye