# Functions and growth rates
\problem
Rank the following functions in terms of growth rate:
Here $[n]$ denotes the set $\{1,2,\cdots,n\}$.
$f_1 = $ ``the number of functions from $[n]$ to $[\sqrt{n}]$''
$f_2 = $ ``the number of functions from $[n/2]$ to $[n]$''
$f_3 = $ ``the number of injective functions from $[n]$ to $[n]$''
$f_4 = $ ``the number of functions from $[n]$ to $[n/2]$''

# From Truss - recurrences and simple counting
\problem
Mary received $\$n$ for her birthday and will spend some of the money each
week until it is all used up.  Each week, Mary will either buy a box of
chocolates (costing $\$1$), go to a movie ($\$2\$), or go to a concert
($\$2$).  If $M_n$ is the number of ways in which Mary can spend her money,
show that:
\[
M_n = M_{n-1} + 2M_{n-2}
\]
Come up with appropriate initial conditions and find a closed-form solution
for $M_n$.
