\documentclass[12pt,a4paper]{amsart}
%%%%%%%%%%% Here is where you tell LaTeX to use packages. Each
%%%%%%%%%%% package gives you access to different commands and
%%%%%%%%%%% functionality. Most of them are unnecessary for the
%%%%%%%%%%% mathematics in this document.

%%%%%%%%%%% If you hadn't figured out, the % symbol automatically
%%%%%%%%%%% nulls out all subsequent characters on that line. So
%%%%%%%%%%% it's used for commenting code.
\usepackage{hyperref}
\usepackage{tikz}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{multicol}
\usepackage[OT2,T1]{fontenc}
\usepackage{graphicx}
\usepackage[all]{xy}
\usepackage{color}
\usepackage{mathrsfs}
\usepackage{mathtools}

%%%%%%%%%%% Determining margins and spacing.
\setlength\topmargin{-0.3in}
\addtolength{\oddsidemargin}{-.625in}
	\addtolength{\evensidemargin}{-.625in}
	\addtolength{\textwidth}{1.25in}
\setlength\footskip{1in}

%%%%%%%%%%% I think this command enables `sections'
\numberwithin{equation}{section}

%%%%%%%%%%% This command allows you to label things as `theorem',
%%%%%%%%%%% `conjecture', etc.
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}{Question}[theorem]
\newtheorem{example}{Example}[theorem]


\usepackage[utf8]{inputenc}
\title{Math 220.201 Class 12 Questions}
\begin{document}
\maketitle

\begin{enumerate}
\item [1.] Let $a_1, a_2, \ldots$ be a sequence defined by $a_1=2$, $a_2=1$, and
$$a_{n+1}=a_n+6a_{n-1}$$
for $n\ge 2$. Prove that, for all $n$, $a_n=3^{n-1}+(-2)^{n-1}$.
\vskip 0.2in
\begin{proof}
We prove this by strong induction on $n$.
\begin{itemize}
\item Base Cases: $n=1, n=2$.
$$3^{1-1}+(-2)^{1-1}=1+1=2$$
$$3^{2-1}+(-2)^{2-1}=3-2=1$$
\item Inductive Step: suppose that $a_k=3^{k-1}+(-2)^{k-1}$ for $k=1, 2, \ldots, n$. We will show that $a_{n+1}=3^n+(-2)^n$. We have that
$$\begin{aligned}
a_{n+1}=a_n+6a_{n-1}&=3^{n-1}+(-2)^{n-1}+6\cdot 3^{n-2}+6\cdot (-2)^{n-2}\\
&= (3+6)3^{n-2}+(-2+6)(-2)^{n-2}\\
&= 9\cdot 3^{n-2}+4\cdot (-2)^{n-2}=3^n+(-2)^n
\end{aligned}$$
This completes the induction.
\end{itemize}
\end{proof}
\vskip 0.2in
\item [2.] Let $a_1, a_2, \ldots$ be a sequence defined by $a_1=1$, $a_2=2$, and
$$a_{n+1}=2a_n-a_{n-1}+2$$
for all $n\ge 2$. Conjecture a formula for $a_n$ and then prove your formula.
\vskip 0.2in
\begin{proof}
We will prove that $a_n=(n-1)^2+1$ for all $n\in\mathbb{N}$. We proceed by induction on $n$.
\begin{itemize}
\item Base cases: $n=1, 2$. $1=0^2+1$ and $2=1^2+1$.
\item Inductive step: suppose that $a_k=(k-1)^2+1$ for $k=1, 2, \ldots, n$. We will show that $a_{n+1}=n^2+1$. We have that
$$\begin{aligned}
a_{n+1}=2a_n-a_{n-1}+2 &= 2(n-1)^2+2-(n-2)^2-1+3\\
&= 2n^2-4n+2-(n^2-4n+4)+3\\
&= n^2+1
\end{aligned}$$
This completes the induction.
\end{itemize}
\end{proof}
\vskip 0.2in
\item [3.] For any positive integer, $n$ is called \emph{prime} if $n\ge 2$ and there exist no integers $a$ such that $1<a<n$ and $a|n$. Prime numbers are usually denoted by the letter $p$.
\vskip 0.2in
Prove that any integer $n\ge 2$ is either prime or can be written as a product of (not necessarily distinct) primes.
\vskip 0.2in
\begin{proof}
Suppose, for a contradiction, that there is some integer greater than or equal to $2$ which is neither prime nor a product of primes. Let $n$ be the least such integer. Then because $n$ is not prime, there exists some $a\in\mathbb{Z}$ such that $1<a<n$ and $a|n$. So there is some $b\in\mathbb{Z}$ such that $n=ab$. Because $a>1$, $b<n$, and because $a<n$, $b>1$. By assumption, $a$ is either prime or is a product of primes. Similarly, $b$ is either prime or is a product of primes. Therefore, $n$ is a product of primes. This contradicts our assumption about $n$.

Therefore, no such $n$ exists, which completes the proof.
\end{proof}
\vskip 0.2in
\item [4.] (Binary Representation) Prove that any positive integer $n$ can be written as
$$n=2^{i_1}+2^{i_2}+\ldots+2^{i_k}$$
for some integers $i_1, \ldots, i_k$ with the property that $0\le i_1<i_2<\cdots<i_k$. (You may assume the fact that for any positive integer $n$, there is a unique greatest integer $i$ such that $2^i\le n$.)

Can you prove this representation is \emph{unique}?
\vskip 0.2in
\begin{proof}
Call a sum of powers of $2$ as shown above \emph{binary representation.} We prove by strong induction on $n$that every positive integer $n$ has a binary representation.
\begin{itemize}
\item Base case: $n=1$. $1=2^0$.
\item Inductive step: Let $n$ be an integer greater than $1$, and suppose that $1, 2, \ldots, n-1$ all have binary representations. Let $i$ be the greatest integer with the property that $2^i\le n$. Then, $n-2^i\ge 0$. If $n-2^i=0$, then we are done as $n=2^i$. If not, then $1\le n-2^i\le n-1$, and therefore $n-2^i$ can be written in the form
$$n-2^i=2^{i_1}+2^{i_2}+\ldots+2^{i_k}$$
where $i_1, i_2, \ldots, i_k$ are integers such that $0\le i_1<i_2<\cdots<i_k$. We have that $i_k<i$, because if $i_k\ge i$, we would have $n-2^i\ge 2^{i_k}\ge 2^i \implies n\ge 2^{i+1}$ which contradicts the maximality of $i$. Therefore,
$$n=2^{i_1}+2^{i_2}+\cdots+2^{i_k}+2^i$$
is a binary representation of $n$. This completes the proof.
\end{itemize}
\end{proof}
\begin{proof} [Proof that binary representation is unique]
Suppose that some positive integer has two binary representations. Let $n$ be the smallest such positive integer, and suppose it has two nonidentical binary representations
$$2^{i_1}+2^{i_2}+\ldots+2^{i_k}=n=2^{j_1}+2^{j_2}+\ldots+2^{j_{\ell}}$$
If $i_1=j_1$, then we have two binary representations
$$2^{i_2}+\ldots+2^{i_k}=n-2^{i_1}=n-2^{j_1}=2^{j_2}+\ldots+2^{j_{\ell}}$$
By the assumption about the minimality of $n$, the two representations must be the same, and therefore, our two binary representations of $n$ are the same, which is a contradiction. Hence, assume that $i_1\neq j_1$. WLOG, $i_1<j_1$. Then
$$2^{i_1}+2^{i_2}+\ldots+2^{i_k} \equiv 2^{i_1}\pmod{2^{i_1+1}}$$
$$2^{j_1}+2^{j_2}+\ldots+2^{j_{\ell}} \equiv 0\pmod{2^{i_1+1}}$$
which is a contradiction, because the two sums are equal. Thus, no such $n$ exists, which proves the result.
\end{proof}
\end{enumerate}
\end{document}