\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}


\begin{document}

\homework{12: Limits of Sequences and Series}{Due Friday, Week 7}

Do \textbf{three} of the following \textbf{six} problems!
\begin{enumerate}
\item Let $\alpha(n)$ denote the number of primes that divide $n$, counting repeated primes once for each repetition.  For example, $\alpha(8) = 3$, while $\alpha(6) = 2$ and $\alpha(13) = 1$.  

Find
\begin{align*}
\lim_{n \to \infty} \frac{\alpha(n)}{n}.
\end{align*}
\item  In class, we will show on Monday that the series $\displaystyle\sum_{n=1}^\infty \frac{1}{n}$ diverges.  Show that the sum
\begin{align*}
\sum_{\substack{n \in \mathbb{N}:\\ n \textrm{ has no 9} \\\textrm{ in its digits}}} \frac{1}{n} 
\end{align*}
converges to some value $< 80$.  

(Hint: For any $k$, how many $k$-digit numbers are there with no 9 in their digits?)
\item In our first full week of classes, we defined the concept of a \textbf{subsequence} as follows: if $\{x_n\}_{n=1}^\infty$ is a sequence, a \textbf{subsequence} of this sequence is any infinite ordered sequence
\begin{align*}
\left( x_{i_1}, x_{i_2}, x_{i_3}, x_{i_4}, \ldots \right)
\end{align*}
where $i_k < i_l$ for all $k < l$.  

For example, the sequence $\{n\cdot (-1)^n\}_{n=1}^\infty = (-1,2,-3,4,-5,6\ldots)$ has $(-1,-3,-5,-7\ldots)$ as a subsequence, as well as $(-1,2,4,6,8,\ldots)$, $(2,-3,4,-5,\ldots)$, and many others!

Suppose that a sequence of real numbers $\{x_n\}_{n=1}^\infty$ is bounded.  Prove that it has a subsequence that converges.

\item Prove or disprove the following claim: there is a sequence $\{a_n\}_{n=1}^\infty$ of real numbers such that for \textbf{any} $r \in \mathbb{R}$, there is a subsequence of $\{a_n\}_{n=1}^\infty$ that converges to $r$.

\item  Suppose you have a $\mathbb{N} \times \mathbb{N}$ grid of $1 \times 1$ squares.  Consider the following game you can play on this board:
\begin{itemize}
\item Starting configuration: put one coin on the square in the bottom-left-hand corner of our board.
\item Moves: suppose that there is a coin on the board such that the squares immediately to its north and east are empty.  Then a valid move is the following: remove this coin from the board, and then put one new coin on the north square and another new coin on the east square.
\end{itemize}
  \begin{center}
    \includegraphics[width=3.0in]{math1d_wk3_coingame1.pdf}
  \end{center}

Is it possible to get all of the coins out of the green region above in a finite number of moves?  Or will there always be coins in that region, no matter what you do?

Hint: one common way that mathematicians try to study games or models like this one is by finding an \textbf{invariant}, i.e. a function or quantity that we can associate to our system that doesn't change after moves are made.  Can you do this here?

\item The following is the first five entries in the \textbf{look-and-say} sequence:
\begin{align*}
& 1,\\
& 11, \\
& 21, \\
& 1211, \\
& 111221,\ldots \\
\end{align*}
To generate the next entry of the ``look-and-say'' sequence from the most recent entry, simply read the last entry aloud, counting the number of digits in groups of that digit.  For example, starting from 111221, we would read
\begin{itemize}
\item 111 is read off as``three ones,'' i.e. 31.
\item 22 is read off as ``two twos,'' i.e. 22.
\item 1 is read off as ``one one,'' i.e. 11.
\end{itemize}
So the next entry in our sequence is 312211.  
\begin{enumerate}
\item Write the next three entries of the look-and-say sequence.
\item Prove that no element of the look-and-say sequence will ever contain a 4.
\end{enumerate}
\end{enumerate}


\end{document}