\documentclass[12pt]{article}

\usepackage[margin=1in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath,amsfonts}
\usepackage{tikz}
\usetikzlibrary{calc}
\usepackage{substr}

\IfSubStringInString{\detokenize{solution}}{\jobname}{%
  % Solutions
  \newcommand\qfill{}
  \newcommand\qpage{}
  \newcommand\qonly[1]{}
  \newcommand\answer[1]{#1}
  \newcommand\question[1]{{\em #1}}
  \newcommand\rubric[1]{}
}
{%
  \newcommand\qfill{\vfill}
  \newcommand\qpage{\newpage}
  \newcommand\qonly[1]{#1}
  \newcommand\answer[1]{}
  \newcommand\question[1]{#1}
  \newcommand\rubric[1]{}
}

\pagestyle{fancy}
\lhead{MATH 387-01}
\chead{Problem Set \#6\answer{ solutions}}
\rhead{\qonly{Name: \framebox{\phantom{Your name goes here}}}}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{{\bf due November 23, 2015}}

\begin{document}
\begin{enumerate}
\item {\bf (10 points)} \question{You open an account at a bank that
    pays 5\% interest yearly, and deposit $a_0$ dollars in it. Every
    year you withdraw \$10 times the number of years you have had the
    account. For example, if you started with \$1000, then in the
    first year you would earn \$50 in interest and withdraw \$10,
    leaving \$1040, and in the second year would earn \$52 and
    withdraw \$20, leaving \$1072, and so forth.

    \begin{enumerate}
    \item \question{Find a recurrence for $a_n$, the balance in the
        account after $n$ years.}

      \answer{Since the balance after $n$ years is 105\% of the
        previous year's balance, minus $\$10n$, we have
        $a_n=1.05a_{n-1}-10n$.}

    \item \question{Solve the recurrence to find a closed form for
        $a_n$.}

      \answer{The associated homogeneous recurrence $b_n=1.05b_{n-1}$
        clearly has general solution $b_n=A1.05^n$ for undetermined
        coefficient $A$. Now we shall find a particular solution to
        the inhomogeneous equation, using the template
        $a^p_n=Bn+C$. Substituting this particular solution into the
        recurrence, we find that
        \begin{align*}
          Bn+C&=1.05(B(n-1)+C)-10n\\
          10n&=0.05Bn+(0.05C-1.05B)
        \end{align*}
        so that $B=200$ and $C=4200$, yielding a particular solution
        $a^p_n=200n+4200$. The general solution is thus
        $a_n=A1.05^n+200n+4200$. Plugging in a particular value of $a_0$, we see that $a_0=A+4200$, so $A=a_0-4200$, leading to the solution
        \[a_n=(a_0-4200)1.05^n+200n+4200.\]}

    \item \question{What is the smallest initial deposit which would
        guarantee that the account never runs out of money?}

      \answer{Over the long term, the balance will be positive or
        negative based on the coefficient of $1.05^n$ in the closed
        form, since this is the dominant term. Thus, in order for the
        bank balance to remain non-negative (and actually positive, as
        it turns out) indefinitely, it must be the case that
        $a_0-4200\geq 0$, so $a_0\geq 4200$. Thus, an initial deposit
        of \$4200 is necessary.}
    \end{enumerate}
}

\item {\bf (10 points)} \question{Let $a_n=8a_{n-1}-16a_{n-2}+3\cdot
    4^n$ with $a_0=3$ and $a_1=-1$. Find a closed form for $a_n$.}

  \answer{The associated homogeneous recurrence,
    $b_n=8b_{n-1}-16b_{n-2}$, has characteristic polynomial
    $\lambda^2=8\lambda-16$, which has a double root at
    $\lambda=4$. Thus, the general solution to the homogeneous
    recurrence is $b_n=A4^n+Bn4^n$.

    Now we shall find a particular solution to the inhomogeneous
    equation. If we were to work in ignorance of our homogeneous
    solution, we would use the template $a^p_n=B4^n$, but must ``bump
    it upwards'' to not overlap our homogeneous solution, and will
    instead consider $a^p_n=Bn^24^n$. Then, substituting this into our
    recurrence:
    \begin{align*}
      Bn^24^n&=8B(n-1)^24^{n-1}-16B(n-2)^24^{n-2}+3\cdot 4^n\\
      16Bn^24^{n-2}&=32B(n^2-2n+1)4^{n-2}-16B(n^2-4n+4)4^{n-2}+48\cdot 4^{n-2}\\
      16Bn^2&=32Bn^2-64Bn+32B-16Bn^2+64Bn-64B+48\\
      32B&=48\\
      B&=\frac32
    \end{align*}
    so $a^p_n=\frac32n^24^n$, leading to the general form
    $a_n=(A+Bn+\frac32n^2)4^n$. We substitute this into our initial
    conditions to get:
    \[\left\{
      \begin{aligned}
        3&=a_0=A\\
        -1&=a_1=4A+4B+6
      \end{aligned}
    \right.\] so that $A=3$ and $B=\frac{-19}4$, leading to the solution 
    \[a_n=\left(3-\frac{19}4n+\frac32n^2\right)4^n.\]
}

\item {\bf (10 points)} \question{We are making bracelets with 6
    stones in a ring, with three different colors of stone. A bracelet
    must contain at least one stone of each color. Two bracelets are
    considered to be identical if one is simply a rotation or a flip
    of the other. How many different bracelets are possible?}

  \answer{The symmetries we want to be considering are those of the
    dihedral group on 6 elements, which contains 12 elements: the
    identity, the clockwise and counterclockwise $60^\circ$ rotations
    $r$ and $r^5$, the clockwise and counterclockwise $120^\circ$
    rotations $r^2$ and $r^4$, and the $180^\circ$ rotation $r^3$, as
    well as the rotations around antipodal stones $f$, $r^2f$, and
    $r^4f$, as well as the rotations around antipodal edges between
    stones $rf$, $r^3f$, and $r^5f$.

    All possible oriented bracelets are invariant under the identity,
    so the number of invariants under the identity is simply the
    ordered selection of six elements form a pool of three
    possibilities, with each needing to be selected at least once;
    this is, as we have seen with the twelvefold way, simply
    $3^6-3\cdot 2^6+3\cdot 1^6=540$.

    Now, we might note that no bracelets are invariant under $r$ or
    $r^5$; such bracelets would need to all be a single color,
    violating the condition that bracelets have stones of all three
    colors. Likewise, $r^2$ or $r^4$ would necessitate bracelets which
    have at most two colors in an alternating ring, so there are also
    no invariants for these.

    Invariance under $r^3$ requires that the bracelet be made up of
    two repetitions of a single pattern of three stones, which is
    possible, and is equal to the number of ways to arrange all three
    stones, which is $6$ (alternatively, we could look at number of
    ways to select ordered stones using each, which would be
    $3^3-3\cdot 2^3+3\cdot 1^3=6$.

    Invariance under $rf$, $r^3f$, and $r^5f$ is quite similar, in
    that the bracelet is defined by the colors on three specific
    stones, and these too have 6 invariants. Finally, $f$, $rf^2$, and
    $rf^4$ involve fixing two stones and mapping the other two pairs
    onto each other, so the bracelet is defined by a selection of 4
    stones, in $3^4-3\cdot 2^4+3\cdot 1^4=36$ ways.

    Now we may use Burnside's Lemma to count the total number of
    possible bracelets:
    \[\frac{540+0+0+6+0+0+36+6+36+6+36+6}{12}=56\]}

\item {\bf (10 points)} \question{A $4\times 4$ grid of squares is
    filled in, with each of the 16 squares colored black or white. Two
    colorings are regarded as identical if one can be converted to
    each other by performing any combination of flipping, rotating, or
    swapping the two colors (flipping all the black squares to white
    and vice versa). How many non-identical colorings are there?}

  \answer{The algebra here is slightly more complicated than simply
    the eight-element group $D_4$; each of those eight elements could
    be composed with a ``color-swap'' to get 16 possible elements; if
    we denote the color-swap as $s$, then these elements could be
    called $e$, $r$, $r^2$, $r^3$, $f$, $rf$, $r^2f$, $r^3f$, $s$,
    $rs$, $r^2s$, $r^3s$, $fs$, $rfs$, $r^2fs$, and $r^3fs$. Every
    single coloring of the $4\times 4$ square is invariant under the
    identity, for a total of $2^{16}=65536$ invariant colorings. To be
    invariant under $r$ or $r^3$, a coloring would have to have the
    same $2\times 2$ block repeated (with appropriate rotations) on
    all four corners, so there are $2^4=16$ invariants. Invariance
    under $r^2$ depends on one half of the grid being identical to the
    appearance on the other half, so there are $2^8=256$
    invariants. Likewise, letting $f$ be a horizontal flip, invariants
    under both $f$ and $r^2f$ are determined by the coloration of half
    (either a vertical or horizontal half) of the grid, so there are
    $2^8=256$ invariants there. $rf$ and $r^3f$ are corner-to-corner
    flips, so they have free choice of color for the four squares
    along their diagonals and then for each of the 6 pairs of
    mirror-image squares off the diagonal, for a total of $10$ choices
    of colors and thus $2^{10}=1024$ invariant colorings.

    Looking at the transformations involving $s$, the exact same
    analysis, simply with a color-transformation added to it, works
    for most of the transformations;
    i.e. $r^2s$ has $2^8$ invariants, $fs$ has $2^8$, $rs$ has $2^4$, etc. However, all of the swapped versions of transformations which leave a square unmoved ($s$, $rfs$, and $r^3fs$) have \emph{no} invariants, since the unmoved square is necessarily a different color after transformation. Thus, applying
    Burnside's lemma gives:
    \[\frac{65536+16+256+16+256+1024+256+1024+0+16+256+16+256+0+256+0}{16}=4324.\]

}
    
\end{enumerate}

\vfill
\begin{center}
  \fbox{
    \begin{minipage}{6in}
      Guided only by their feeling for symmetry, simplicity, and
      generality, and an indefinable sense of the fitness of things,
      creative mathematicians now, as in the past, are inspired by the
      art of mathematics rather than by any prospect of ultimate
      usefulness.\\
      \phantom0\hfill ---Eric Temple Bell
    \end{minipage}
  }
\end{center}

\end{document}
