% If you are working from this template to just write up your own
% solutions, I'm trying to keep it simple for you and there are only a
% few places you need to edit. On line 43 there's a place where the
% phrase "YOUR NAME HERE" appears; change it to your actual
% name. Several places below there are places where the phrase "YOUR
% ANSWER HERE" appears, and directly below (or replacing) those lines
% are good places to put your answers.
%
% One important thing you need to do, however (due to the complicated
% way I use a single form to produce both the question sheets and
% solution writeups) is to make sure that you keep the word 'solution'
% in your filename, or else your answers won't be printed at all.
\documentclass[12pt]{article}
 
\usepackage[margin=0.7in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{tikz}
\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]{}
}
{%
  % Question sheets
  \newcommand\qfill{\vfill}
  \newcommand\qpage{\newpage}
  \newcommand\qonly[1]{#1}
  \newcommand\answer[1]{}
  \newcommand\question[1]{#1}
  \newcommand\rubric[1]{}
}

\pagestyle{fancy}
\lhead{MATH 311-01}
\chead{Problem Set \#8\answer{ solutions}}
\rhead{\answer{}}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{{\bf due March 23, 2017}}

\newtheorem{prop}{Proposition}

% The command below redefines \neg (the logical negation character)
% to be a big tilde, in line with the usage in the book. Comment it
% out if you prefer the more traditional negation symbol.
\renewcommand*{\neg}{\mathord{\sim}}

\begin{document}
\qonly{For the following proofs, induction is the suggested
  method; if you find that another approach works better, you are
  welcome to use it, but proof by induction is probably the best
  approach.}

\begin{enumerate}
\item \question{Prove that 
    \[1+4+9+\cdots+n^2=\frac{n(n+1)(2n+1)}6.\]}
  
  \answer{
    \begin{proof}
      We proceed by induction on $n$. For the base case $n=1$, we may
      simply observe that $1=\frac{1(1+1)(2+1)}6$. For our inductive
      step, we may assume that for a specific $k$, it is true that
      \[1+4+9+\cdots+k^2=\frac{k(k+1)(2k+1)}6.\]
      And we wish to show (although we do not yet know it to be true!) that
      \[1+4+9+\cdots+(k+1)^2=\frac{(k+1)(k+2)(2k+3)}6.\]
      To work from the inductive hypothesis to the desired conclusion,
      we will add $(k+1)^2$ to both sides of the equation and
      algebraically rearrange the right side.  
      \begin{align*}
        1+4+9+\cdots+k^2+(k+1)^2&=\frac{k(k+1)(2k+1)}6+(k+1)^2\\
        &=\frac{(k+1)(2k^2+k)+6(k+1)(k+1)}6\\
        &=\frac{(k+1)(2k^2+7k+6)}6\\
        &=\frac{(k+1)(k+2)(2k+3)}6\\
      \end{align*}
      and our desired conclusion has thus been shown.
    \end{proof}
  }

\item \question{Let the sequence $a_1,a_2,a_3,\ldots$ be determined by
    the recurrence relation $a_1=2$, $a_2=3$, $a_n=a_{n-1}+6a_{n-2}$
    for each $n\geq 2$.

    Prove that for every natural number $n$,
    $a_n=\frac{14\cdot 3^n-9(-2)^n}{30}$.}
  
  \answer{
    \begin{proof}
      We proceed by (total) induction on $n$. For the base cases $n=1$
      and $n=2$, we may simply observe that $2=\frac{14\cdot
        3-9(-2)}{30}$ and $3=\frac{14\cdot 9-9\cdot 4}{30}$. For our
      inductive step, we may assume that for a specific $k$, every
      $n<k$ satisfies
      \[a_n=\frac{14\cdot 3^n-9(-2)^n}{30}.\] Specifically, since
      $a_k=a_{k-1}+6a_{k-2}$, it will be especially useful to know
      that
      \[a_{k-1}=\frac{14\cdot 3^{k-1}-9(-2)^{k-1}}{30}\text{ and }
      a_{k-2}=\frac{14\cdot 3^{k-2}-9(-2)^{k-2}}{30}.\] Now we can
      arithmetically expand the expression which represents $a_k$, in
      the hopes of arriving at our desired conclusion:
      \begin{align*}
        a_k&=a_{k-1}+6a_{k-2}\\
        &=\frac{14\cdot 3^{k-1}-9(-2)^{k-1}}{30}+6\frac{14\cdot 3^{k-2}-9(-2)^{k-2}}{30}\\
        &=\frac{\frac{14}3\cdot 3^k+\frac92(-2)^k+\frac{14\cdot 6}9\cdot 3^k-\frac{9\cdot 6}4(-2)^k}{30}\\
        &=\frac{14\left(\frac13+\frac23\right)3^k+9\left(\frac12-\frac32\right)(-2)^k}{30}\\
        &=\frac{14\cdot3^k-9(-2)^k}{30}\\
      \end{align*}
      which is the inductive conclusion required.
    \end{proof}
    Note, incidentally, that since each $a_n$ can be easily shown to
    be an integer and since $14\cdot 3^n-9(-2)^n=30a_n$, we have
    shown, among other things, that $30\mid 14\cdot 3^n-9(-2)^n$.

  }

\item \question{Prove that for each natural number $n$,
    \[\frac11+\frac12+\frac13+\cdots+\frac1{2^n}\geq 1+\frac n2.\]
  }

  \answer{
    \begin{proof}
      We proceed by induction on $n$. For the base case $n=1$, it
      suffices to show the arithmetically trivial truth
      $\frac11+\frac12\geq 1+\frac12$.
      Now, we shall inductively assume the hypothesis that for a specific $k$,
      \[\frac11+\frac12+\frac13+\cdots+\frac1{2^k}\geq 1+\frac k2.\]
      and we wish to explore the sum
      $\frac11+\frac12+\cdots+\frac1{2^{k+1}}$. We can do this by
      adding $2^k$ additional terms to the series on both sides of the
      inequality.
      \[\frac11+\frac12+\frac13+\cdots+\frac1{2^k}+\frac1{2^k+1}+\frac1{2^k+2}+\cdots+\frac1{2^{k+1}}\geq 1+\frac k2+\frac1{2^k+1}+\frac1{2^k+2}+\cdots+\frac1{2^{k+1}}\]
      We may note that every single one of the terms $\frac1{2^k+1}, \frac1{2^k+2},\cdots,\frac1{2^{k+1}}$ has a denominator which
      is less than or equal to $2^{k+1}$, so that each fraction itself
      will be at least $\frac1{2^{k+1}}$. We can thus place a lower
      bound on the right side of the above equation:
      \[1+\frac
      k2+\frac1{2^k+1}+\frac1{2^k+2}+\cdots+\frac1{2^{k+1}}\geq
      1+\frac
      k2+\underbrace{\frac1{2^{k+1}}+\frac1{2^{k+1}}+\cdots+\frac1{2^{k+1}}}_{2^k\text{
          times}}\] Note that the terms we bounded thus are the
      $(2^k+1)$th to the $(2^{k+1})$th, for a total of
      $2^{k+1}-2^k=2^k$ terms. Since the upper bounds are all equal,
      we can collapse this repeated sum into a multiplication by the
      number of terms:
      \[1+\frac
      k2+\frac1{2^k+1}+\frac1{2^k+2}+\cdots+\frac1{2^{k+1}}\geq
      1+\frac k2+2^k\cdot\frac1{2^{k+1}}=1+\frac
      k2+\frac12=1+\frac{k+1}2\] and this yields the desired inductive
      conclusion by an appropriate transitive processing of the
      inequality.
    \end{proof}
    Incidentally, the above proof can serve to show that the infinite
    sum $1+\frac12+\frac13+\frac14+\frac15+\cdots$ diverges; this sum
    is known as the \emph{harmonic series} and it is a significant
    example in the study of sequences and series (specifically, it is
    a series whose terms dwindle towards zero, but whose sum
    nonetheless continues to grow without bound).
  }

\item \question{Prove that for any nonnegative integer $n$, it is the
    case that $9\mid (4^{3n}+8)$.}

  \answer{
    \begin{proof}
      For the base case $n=0$, note that $4^0+8=9$, which is indeed
      divisible by 9. We now inductively assume that for a specific
      $k$, $9\mid 4^{3k}+8$. Thus there is an integer $\ell$ such that
      $4^{3k}+8=9\ell$. We shall now try to build $4^{3(k+1)}+8$
      arithmetically; note that $4^{3(k+1)}=4^{3k}4^3$, so we multiply
      by $64$ to get $4^{3k+3}+512=576\ell$. To get an $8$ instead of
      $512$ on the left side, we can subtract $504$ to get
      $4^{3(k+1)}+8=576\ell-504=9(64\ell-56)$. Thus $9\mid
      4^{3(k+1)}+8$.
    \end{proof}
  }
\end{enumerate}

\end{document}
