<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[UTF8, 11pt]{amsart}
\usepackage{hyperref}
\usepackage{amsthm}

\title{MATH 3040: Homework 4}
\author{}
\date{September 13, 2017}

%----------Theorems----------

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{nondefinition}[theorem]{Non-Definition}
\newtheorem{exercise}[theorem]{Exercise}

\newcommand{\N}{\textbf{N}}
\newcommand{\Z}{\textbf{Z}}

%Redefine the first level
\renewcommand{\theenumi}{(\alph{enumi})}
\renewcommand{\labelenumi}{\theenumi}

\begin{document}

\maketitle

All answers must be in complete sentences. Remember that this is a writing class, so while correctness and thoroughness are most important, \textit{style} matters as well. 

For some problems, it may be useful to use a variant of induction called \textbf{strong induction}. (See [TAP, \S 4.5] for details.)


\bigskip
\noindent
\textbf{1. (Practice in Posing Questions)} What is an interesting open-ended question you could ask, which is related to the material that we covered in class? What is a concrete mathematical question that could be used to approach an answer to the question? 


\bigskip
\noindent
\textbf{2. (Fibonacci Numbers)} The Fibonacci sequence $F_i$ is a sequence of numbers defined recursively by $F_1 = 1$, $F_2 = 2$, and $F_{n+2} = F_n + F_{n+1}$ for $n \geq 1$.
\begin{enumerate}
  % a
  \item{Show by induction on $n$ that
  \[
  F_n  &lt; \left(\frac{1 + \sqrt{5}}{2} \right)^n.
  \]}	

  
  % b
  \item{Prove that $F_n$ is the closest integer to
  \[
  \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^{n+1}.
  \]
  (This allows us to compute $F_n$ even faster than the formula in Prop. 4.29 of [TAP].)}
  
  % c
  \item{For all $n \in \N$, we have $F_{2n+1} = F_n^2 + F_{n+1}^2$.}
\end{enumerate}


\medskip
\noindent
\textit{Remark.} The number $\varphi = \frac{1 + \sqrt{5}}{2}$ is known as the \textit{golden ratio}, and shows up in a number of natural processes and in many things that we as humans consider to be aesthetically pleasing.


\bigskip
\noindent
\textbf{3. (Finding Formulas)}  Suppose that $n \in \N$. Find and prove a closed formula (e.g. $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$) for each of the following expressions.
\begin{enumerate}
  \item{$1 + 2 + 4 + 8 + \cdots + 2^n$.}
  \item{$1 \cdot 1! + 2 \cdot 2! + 3 \cdot 3! + \cdots + n \cdot n!$ (Recall that factorials are defined as, e.g. $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$.)}
  \item{$\frac{1}{2} + \frac{1}{6} + \frac{1}{12} + \cdots + \frac{1}{n(n+1)}$}
  
  \item{$\frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!} + \cdots + \frac{n}{(n+1)!}$.}
  
  \item{$(1 - \frac{1}{4})\cdot(1 - \frac{1}{9}) \cdots (1 - \frac{1}{(n+1)^2})$.}	
\end{enumerate}



\bigskip
\noindent
\textbf{4. (Discover the truth, and prove it!)} For each of the following, determine (with proof) the set of \textit{all} natural numbers $n$ for which the statement holds.
\begin{enumerate}
  % a 
  \item{$2^n &lt; n!$}
  % b
  \item{$2^n &gt; n^2$}
  % c
  \item{$3^n + 5$ is divisible by 8. (Hint: $3^{k+2} + 5 = (3^k + 5) + 8 \cdot 3^k$ for every $k \in \N$)}
  % d
  \item{$3^n + 4^n$ is divisible by 13.}	
\end{enumerate}
 



\bigskip
\noindent
\textbf{5. (Induction and Beyond)} 
\begin{enumerate}
  \item{Define an infinite sequence $(a_1, a_2, a_3, \ldots)$ recursively by $a_1 = 2$, $a_{n+1} = a_n + 2n$ for all $n \in \N$. Find and prove an explicit formula for $a_n$ (i.e. a formula in terms of $n$ only).}
  \item{Find a formula for the number of regions created by $n$ pairwise intersecting circles in the plane in general position (i.e. every pair of circles intersects in two points and no three of the circles intersect at the same point).}
\end{enumerate}


\bigskip
\bigskip
The following problem should be submitted as a group. Modify the groupwork template tex file accordingly. You can look at the .tex file for this homework assignment if you don't want to retype it in.

\bigskip
\noindent
\textbf{6. (Groupwork) [Survivors among the natural numbers]} Given positive integers $x_1, x_2, \ldots, x_n$, let $A(x_1, \ldots, x_n)$ be the set of natural numbers that can be written as a sum of (positive) multiples of the $x_i$'s, that is, in other words, every number $n \in \N$ of the form
\[
n = a_1 \cdot x_1 + a_2 \cdot x_2 + \cdots + a_n \cdot x_n
\]
for any $a_1, \ldots, a_n \in \N$ is contained in $A(x_1, \ldots, x_n)$. Define the \textbf{last survivor number} $S(x_1, \ldots, x_n)$ of $x_1, x_2, \ldots, x_n$ to be the maximum element of $\N$ that is \textit{not} contained in $A(x_1, \ldots, x_n)$, if it exists.

\begin{enumerate}
  % a
  \item{Explain why $S(x_1, x_2, \ldots, x_n)$ can only exist if $x_1, x_2, \ldots, x_n$ are relatively prime (i.e. no two numbers share a common factor). (\textit{Fun fact}. The converse statement is true: if the integers are relatively prime, then the last survivor number exists.)}
  
  % b
  \item{Prove that $S(4,5) = 11$.}
  
  % c
  \item{Find $S(3,10)$ and prove your answer.}
  
  % d
  \item{Find $S(3,5,7)$ and prove your answer.}
  
  % e
  \item{Find $S(7, 19, 37)$ and prove your answer.}
  
  % f
  \item{Assume that $a$ and $b$ are relatively prime. Formulate a conjecture for what $S(a,b)$ should be, in terms of $a$ and $b$. (You do not need to prove your claim.)}
  
  % g
  \item{Assume that $a$ and $b$ are relatively prime. Formulate a conjecture for the number of \textbf{survivors} (i.e. the natural numbers that do not lie in $A(a,b)$), in terms of $a$ and $b$. (You do not need to prove your claim.)}
  

\end{enumerate}

 

\end{document}
</pre></body></html>