\magnification=\magstephalf
\voffset=-.45truein
\vsize=10.6truein
%\hoffset=-.4truein \hsize=7truein
%\baselineskip=10.5truept
%\lineskiplimit=-100pt
\nopagenumbers
%\parskip=1pt
\font\eightrm=cmr7

\centerline{HOMEWORK SET \#5 / CO1A / Spring 2020} \vskip4mm
\item{1.)} Solve the recurrence relation under the given initial
conditions: $k_n=k_{n-1}+n+6$, $k_0=0$.
\item{2.)} Determine a recurrence for $f(n)$, the number of regions
into which the plane is divided by $n$ circles in general position
(circles are in general position if each two intersect in two points and no three share a common point).
Solve the recurrence to obtain the number of parts.

\item{3.)}Solve the recurrence relation under the given initial
conditions: $a_{n+2}=2a_{n}-a_{n+1}+3\cdot(-2)^n$,
$a_0=-1,\,a_1=1$.

\item{4.)}  Solve the recurrence relation under the given initial
conditions: $h_{k+2}=2h_{k+1}-h_k+2^k$, $h_0=2,\,h_1=1$.


\item{5.)} Find both the recurrence relation and the appropriate
generating function for the number of n-digit numbers (over
$\{0,1,\ldots,9\}$) where digit 0 can be used only even number of
times. Use the generating function to find the number!

\item{6.)} Let $D_n$ denote the number of derangaments of $n$ objects. Let $C_n$ be defined by
$$C_n={D_n \over n!}-{D_{n-1} \over (n-1)!}.$$
 Find a recurrence for $C_{n+1}$ in terms of $C_n$, solve it (using iteration) and use expression for $C_n$ to express $D_n$.


\item{7.)}  Prove that $x^n= \sum_{k=1}^n S(n,k)x(x-1)\cdots
(x-k+1)$ (Hint: prove that the two polynomials on the two sides of
the equation are equal at values $x=0,1,2,\ldots,n$.)
\item{8.)}
 For each of the following functions, find the sequences for
which  the function is the ordinary and (for a different
sequence) the exponential generating function:
  ${1\over 1-x}+e^{6x}$ ,\ \ \ \  $(1+x^2)^n+1$,\ \ \ \  $e^{x/2}+x^2+x^3$

  \vfill

  \centerline{HOMEWORK SET \#5 / CO1A / Spring 2020} \vskip4mm
\item{1.)} Solve the recurrence relation under the given initial
conditions: $k_n=k_{n-1}+n+6$, $k_0=0$.
\item{2.)} Determine a recurrence for $f(n)$, the number of regions
into which the plane is divided by $n$ circles in general position
(circles are in general position if each two intersect in two points and no three share a common point).
Solve the recurrence to obtain the number of parts.

\item{3.)}Solve the recurrence relation under the given initial
conditions: $a_{n+2}=2a_{n}-a_{n+1}+3\cdot(-2)^n$,
$a_0=-1,\,a_1=1$.

\item{4.)}  Solve the recurrence relation under the given initial
conditions: $h_{k+2}=2h_{k+1}-h_k+2^k$, $h_0=2,\,h_1=1$.


\item{5.)} Find both the recurrence relation and the appropriate
generating function for the number of n-digit numbers (over
$\{0,1,\ldots,9\}$) where digit 0 can be used only even number of
times. Use the generating function to find the number!

\item{6.)} Let $D_n$ denote the number of derangaments of $n$ objects. Let $C_n$ be defined by
$$C_n={D_n \over n!}-{D_{n-1} \over (n-1)!}.$$
 Find a recurrence for $C_{n+1}$ in terms of $C_n$, solve it (using iteration) and use expression for $C_n$ to express $D_n$.


\item{7.)}  Prove that $x^n= \sum_{k=1}^n S(n,k)x(x-1)\cdots
(x-k+1)$ (Hint: prove that the two polynomials on the two sides of
the equation are equal at values $x=0,1,2,\ldots,n$.)
\item{8.)}
 For each of the following functions, find the sequences for
which  the function is the ordinary and (for a different
sequence) the exponential generating function:
  ${1\over 1-x}+e^{6x}$ ,\ \ \ \  $(1+x^2)^n+1$,\ \ \ \  $e^{x/2}+x^2+x^3$



\bye
