% Homework 6, 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} (92~points)}
\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$.

\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$?}
}}

\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?

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

\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?

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

\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$.

\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$.

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

\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.

\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.

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

\bye