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


\usepackage{tikz}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\input{preamble.tex}

\begin{document}

\homework{7: Other Famous Numbers}{Due Friday, Week 4}

Over the past week, we've studied the Catalan numbers, one of the most famous sequences of integers in combinatorics.  On this set, you'll study some other famous numbers!  Each problem will introduce a class of numbers, and mention one or two interesting properties which you are then invited to prove.

Several problems here have extra-credit parts, or are extra-credit themselves.  You do not need to do these parts to get full credit for the problem.

Also, because these problems are all multi-part and this set came out a little late, we're asking you to do just two of these problems, instead of the usual three.  Solve \textbf{two} of the \textbf{five} problems below!

\begin{enumerate}
\item Recall, from earlier in class, the definition of a \textbf{partition} of a set:
\begin{defn}
Given any set $S$, a \textbf{partition} of $S$ into $n$ pieces is a way to write $S$ as the union of $n$ disjoint sets $A_1, \ldots A_n$, such that all of the $A_i$ sets are mutually disjoint (i.e. none of these sets overlap), none of the $A_i$ are empty, and the union of all of them is our set $S$.

For example, if $S = \{1,2,3, $ fish, $ 6, 7,8\} $, a partition of $S$ into three parts could be given by
\begin{align*}
A_1 = \{1,8\},  A_2 = \{\textrm{fish}\}, A_3 = \{2,3,6,7\}.
\end{align*}

We define the \textbf{Bell number} $B_n$ as the number of different partitions of a set of $n$ elements into any number of parts.  For example, $B_2 = 2$ because a set with two elements can be partitioned in exactly two ways:
\begin{align*}
S = \{1,2\}: \{1\} \cup \{2\} \textrm{ or } \{1,2\}.
\end{align*}
\begin{enumerate}
\item Find $B_3$.
\item Show that the Bell numbers satisfy the recurrence relation
\begin{align*}
B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k.
\end{align*}
\item Show that $B_{n-1}$ is even if and only if $n$ is a multiple of 3.  (That is; $B_2, B_5, B_8, \ldots$ and so on should all be even, and all other Bell numbers should be odd.)

Hint: Prove the following useful theorem:
\begin{thm}
For any natural number $n$, we have $B_{n+2} = B_n + B_{n+1} \mod 2$.
\end{thm}
Hint for this theorem: consider partitions of the set $\{1,2,\ldots n, a, b\}$.  There are three kinds of partitions:
\begin{enumerate}
\item Partitions where both $a, b$ land in the same set. 
\item Partitions where $a$ lands in a singleton set $\{a\}$ and $b$ lands in a singleton set $\{b\}$.
\item Other partitions: i.e. partitions where $a, b$ land in different sets, but at least one of those sets is not a singleton set.
\end{enumerate}
Explain why there are always an even number of these ``other'' partitions.  Conclude from this that $B_{n+2} = B_n + B_{n+1} \mod 2$.
\end{enumerate}
\end{defn}

\item The \textbf{Triangular numbers} $T_n$ are given by the number of coins that you need to stack in two dimensions to create an equilateral triangle:
\begin{center}
\includegraphics[width=2in]{First_six_triangular_numbers.pdf}
\end{center}
\begin{enumerate}
\item Show that $T_n = \frac{n(n+1)}{2}$ for any $n$.
\item Take any $n \in \mathbb{N}$.  Show that you can write $n$ as a sum of at most six triangular numbers.

Hint, to make this problem actually doable (it was too hard earlier:) you may use the following theorem without proof.
\begin{thm}
(Lagrange.) Any natural number $n$ can be written as the sum of four squares of natural numbers.
\end{thm}
\end{enumerate}

\item In class, we studied the Fibonacci sequence $\{f_n\}_{n=0}^\infty$.  
\begin{enumerate}
\item Prove that if $n$ is a composite\footnote{A natural number $n$ is composite if we can write $n = lk$, for two other natural numbers $k,l$.} number, then $f_n$ is also a composite number, for $n \geq 5$.
\item Show that the converse does not hold: i.e. find a prime number $p$ such that $f_p$ is not prime.
\item (Extra credit.  Also hard.)  Find infinitely many Fibonacci numbers that are primes, or prove that this is impossible.
\end{enumerate}
\item  \textbf{Pascal's triangle} is a triangular array formed by the binomial coefficients:
\begin{center}
\includegraphics[width=1.4in]{pascal1.pdf}
\end{center}
In general, the $n$-th row of Pascal's triangle is given by the $n+1$ binomial coefficients
\begin{align*}
\binom{n}{0} ~~ \binom{n}{1} ~~ \binom{n}{2} ~~ \ldots ~~ \binom{n}{n-2} \binom{n}{n-1} ~~ \binom{n}{n}
\end{align*}
\begin{enumerate}
\item Prove that in Pascal's triangle, each entry is the sum of the two entries above it.
\item Let's consider the Fibonacci sequence $\{f_n\}_{n=0}^\infty$ again.  Prove the identity
\begin{align*}
f_{n+1} = \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k}.
\end{align*}
For example,
\begin{align*}
21 = f_8 = \sum_{k=0}^{\lfloor (7-1)/2\rfloor} \binom{7-k}{k} = \binom{7}{0} + \binom{6}{1} + \binom{5}{2} + \binom{4}{3} = 1 + 6 + 10 + 4 = 21.
\end{align*}
\item For the Fibonacci numbers $f_1, f_2, f_3, f_4$, circle for each number the binomial coefficients associated to that Fibonacci number in the sum in (b).  What pattern do you see?  Explain your observation.
\end{enumerate}
\item The \textbf{Pell numbers} are defined by the following recurrence relation:
\begin{align*}
P_0 = 0, P_1 = 1, P_n = 2p_{n-1} + P_{n-2}.
\end{align*}
The first few Pell numbers are $0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, \ldots$
\begin{enumerate}
\item Using generating functions, find a closed form for the Pell numbers (like how we did for the Fibonacci sequence.)  If you've done this right, there should be $\sqrt{2}$'s in your answer.
\item An alternate definition for the Pell numbers is the following, based on the idea of ``approximating $\sqrt{2}$.''  

For any $k$, define $r(k)$ to be an integer such that $\frac{r(k)}{k}$ is as close to $\sqrt{2}$ as possible.  For example, $r(1) = 1,$ because $1/1$ is the closest fraction to $\sqrt{2}$ that you can make with denominator 1.  Similarly, $r(2) = 3$, because $3/2$ is the closest fraction with denominator 2, $r(3) = 4$, $r(4) = 6$, $r(5) = 7$, and so on/so forth.

Look at the sequence given by $\{\frac{r(k)}{k}\}_{k=1}^\infty$:
\begin{align*}
\frac{1}{1}, \frac{3}{2}, \frac{4}{3}, \frac{6}{4}, \frac{7}{5}, \ldots
\end{align*}
Notice that when we do this, some of our approximations are ``better'' than others.  That is: $3/2$ is closer to $\sqrt{2}$ than $\frac{4}{3}$.  So: get rid of all of the approximations that are worse than earlier approximations!  In other words, form the sequence $\left\{\frac{p_n}{q_n}\right\}_{n=1}^\infty$ of ``increasingly better approximations,'' defined as follows: $\frac{p_1}{q_1} = 1$, and
\begin{align*}
\frac{p_n}{q_n} = \textrm{ the smallest value of }k\textrm{ such that }\left|\frac{r(k)}{k} - \sqrt{2}\right| < \left| \frac{p_{n-1}}{q_{n-1}} - \sqrt{2} \right|.
\end{align*}
Look at the first few terms of this sequence:
\begin{align*}
\frac{1}{1}, \frac32, \frac75, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \ldots
\end{align*}
Funny thing: the denominators of these fractions are the Pell numbers! Explain why this is true.
\end{enumerate}


\item (Extra credit.  Harder than the other hard extra credit problems.)  Consider the following function $f: \mathbb{N} \to \mathbb{N}$:
\begin{align*}
f(n) = \left\{\begin{array}{cc} n/2, & \textrm{ if } n \textrm{ is even, or}\\ 3n+1 & \textrm{ if } n \textrm{ is odd.}\end{array} \right.
\end{align*}
Using this function, for any $n$, we can define its corresponding ``hailstone-sequence:''
\begin{align*}
(n, f(n), f(f(n)), f(f(f(n))), \ldots)
\end{align*}
For example, $n=6$ has the following corresponding sequence:
\begin{align*}
(6,3,10,5,16,8,4,2,1,4,2,1,4,2,1,\ldots)
\end{align*}
Notice that if we ever get to 1, our sequence ``repeats'' the $4-2-1$ loop forever.  We call such sequences \textbf{terminating,} as we can effectively cut them off when they get to 1 and lose no information.
\begin{enumerate}
\item Show that there are infinitely many terminating numbers.
\item Either find a nonterminating number, or prove no such number can exist.
\end{enumerate}
\end{enumerate}



\end{document}