\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 \#4 / CO1A / Spring 2020} \vskip4mm
\item{1.)} Solve the recurrence relation under the given initial
conditions: \quad  $a_k=6a_{k-1}-11a_{k-2}+6a_{k-3},\break
a_0=1,\;a_1=4,\;a_2=9.$
\vskip8pt
\item{2.)} Remember that the Fibonacci numbers are defined by
$F_{n}=F_{n-1}+F_{n-2}$ and $F_0=F_1=1$. Find closed formulas for
 $F_0+F_2+F_4+\cdots+F_{2n}$,
$F_1+F_3+F_5+\cdots+F_{2n+1}$ and $F_0+F_1+F_2+\cdots +F_n$ ($n\ge
1$) (you may express them sums in terms of some --- fixed number
of --- members of the Fibonacci sequence).
\item{3.)} Determine a recurrence for $f(n)$, the number of regions
into which the space is divided by $n$ planes in general position
(and for that define the general positions of the planes as well
such a way that they will give the highest possible numbers of
parts of the plane). Solve the recurrence to obtain the number of
parts.
\item{4.)} How many subsets does the set $\{1,2,\ldots, n\}$ have
that contain no two consecutive integers?

\item{5.)} Solve the recurrence relation under the given initial
conditions: $c_n=9c_{n-1}-15c_{n-2}+7c_{n-3},$\break $c_0=0,\
c_1=1,\ c_2=2$.

\item{6.)} We have $n$ forints. Every day we buy exactly one of
the following products: pretzel (1 forint), candy (2 forints),
icecream (2 forints). What is the number of possible ways of
spending all the money (the order of the bought products counts)?

\item{7.)} Remember that the Fibonacci numbers are defined by
$F_{n}=F_{n-1}+F_{n-2}$ and $F_0=F_1=1$. Prove that for every pair
$m\ge 0$,\ \ $n>0$ \ $F_{n+m+1}=F_{n-1}F_m+F_nF_{m+1}$.

\item{8.)}  Prove that the number of partitions of a number $n$
into no more than $r$ terms is equal to the number of partitions
of $n$ into any number of terms, each at most $r$. (A partition
of a number $n$ into $r$ terms is a collection
 of positive integers $\{a_1,a_2,a_3,\ldots,a_r\}$ such that
$a_1+a_2+\cdots+a_r=n$; note that order does not count!)



\vfill\vfill
\centerline{HOMEWORK SET \#4 / CO1A /Spring 2020} \vskip4mm
\item{1.)} Solve the recurrence relation under the given initial
conditions: \quad  $a_k=6a_{k-1}-11a_{k-2}+6a_{k-3},\break
a_0=1,\;a_1=4,\;a_2=9.$
\vskip8pt
\item{2.)} Remember that the Fibonacci numbers are defined by
$F_{n}=F_{n-1}+F_{n-2}$ and $F_0=F_1=1$. Find closed formulas for
 $F_0+F_2+F_4+\cdots+F_{2n}$,
$F_1+F_3+F_5+\cdots+F_{2n+1}$ and $F_0+F_1+F_2+\cdots +F_n$ ($n\ge
1$) (you may express them sums in terms of some --- fixed number
of --- members of the Fibonacci sequence).
\item{3.)} Determine a recurrence for $f(n)$, the number of regions
into which the space is divided by $n$ planes in general position
(and for that define the general positions of the planes as well
such a way that they will give the highest possible numbers of
parts of the plane). Solve the recurrence to obtain the number of
parts.
\item{4.)} How many subsets does the set $\{1,2,\ldots, n\}$ have
that contain no two consecutive integers?

\item{5.)} Solve the recurrence relation under the given initial
conditions: $c_n=9c_{n-1}-15c_{n-2}+7c_{n-3},$\break $c_0=0,\
c_1=1,\ c_2=2$.

\item{6.)} We have $n$ forints. Every day we buy exactly one of
the following products: pretzel (1 forint), candy (2 forints),
icecream (2 forints). What is the number of possible ways of
spending all the money (the order of the bought products counts)?

\item{7.)} Remember that the Fibonacci numbers are defined by
$F_{n}=F_{n-1}+F_{n-2}$ and $F_0=F_1=1$. Prove that for every pair
$m\ge 0$,\ \ $n>0$ \ $F_{n+m+1}=F_{n-1}F_m+F_nF_{m+1}$.

\item{8.)}  Prove that the number of partitions of a number $n$
into no more than $r$ terms is equal to the number of partitions
of $n$ into any number of terms, each at most $r$. (A partition
of a number $n$ into $r$ terms is a collection
 of positive integers $\{a_1,a_2,a_3,\ldots,a_r\}$ such that
$a_1+a_2+\cdots+a_r=n$; note that order does not count!)

\bye
