\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 10 Questions}
\begin{document}
\maketitle
Use induction to prove the following results.
\begin{enumerate}
\item [1.] For all $n\in\mathbb{N}$, $1+2+3+\ldots+n=\frac{n(n+1)}{2}$.
\vskip 0.2in
Note: as this is the first induction proof, I will make it extra-explicit.
\begin{proof}

Let $P(n)$ be the sentence ($1+2+\ldots+n=\frac{n(n+1)}{2}$). We wish to prove $\forall n\in\mathbb{N}, P(n)$. We prove this by induction on $n$.
\begin{itemize}
\item {\bf Base Case: $P(1)$.} This is equivalent to showing that $1=\frac{1\cdot 2}{2}$. This is clear.
\item {\bf Inductive Step: $\forall n\in\mathbb{N}, P(n)\implies P(n+1)$.} We must prove that for any $n$, if $P(n)$ is true, then $P(n+1)$ is true. Suppose that $P(n)$ is true, i.e. $1+2+\ldots+n=\frac{n(n+1)}{2}$.\footnote{This is called the \emph{inductive hypothesis.}} Then
$$\begin{aligned}
1+2+\ldots+n+(n+1)&=1+2+\ldots+n+(n+1) & \\
&= \frac{n(n+1)}{2}+(n+1) & \text{by the inductive hypothesis}\\
&= \frac{n(n+1)}{2}+\frac{2(n+1)}{2} &\\
&= \frac{(n+1)(n+2)}{2}&
\end{aligned}$$
Therefore, we have proven $P(n+1)$. This completes the induction, and therefore completes the proof.
\end{itemize}
\end{proof}
\vskip 0.2in
\item [2.] For all $n\in\mathbb{N}$, $1^2+2^2+3^2+\ldots+n^2=\frac{n(n+1)(2n+1)}{6}$.
\vskip 0.2in
\begin{proof}
We prove it by induction on $n$. Let $P(n)$ be the sentence ($1^2+2^2+\ldots+n^2=\frac{n(n+1)(2n+1)}{6}$).
\begin{itemize}
\item {\bf Base Case: $P(1)$.} We must check that $1^2=\frac{1\cdot 2\cdot 3}{6}$. This is clear.

\item {\bf Inductive Step: $P(n)\implies P(n+1)$.} Suppose that $1^2+2^2+\ldots+n^2=\frac{n(n+1)(2n+1)}{6}$ is true. Then
$$\begin{aligned}
1^2+2^2+\ldots+n^2+(n+1)^2 &= \frac{n(n+1)(2n+1)}{6}+(n+1)^2 & \text(by inductive hypothesis)\\
&= \frac{(n+1)(2n^2+n)}{6}+\frac{(n+1)(6n+6)}{6} &\\
&= \frac{(n+1)(2n^2+7n+6)}{6} &\\
&= \frac{(n+1)(n+2)(2n+3)}{6} &\\
&= \frac{(n+1)((n+1)+1)(2(n+1)+1)}{6} &
\end{aligned}$$
which proves $P(n+1)$. This completes the induction.
\end{itemize}
\end{proof}
\vskip 0.2in
\item [3.] Let $x>-1$ be a real number. Then for all $n\in\mathbb{N}, (1+x)^n\ge 1+nx$.
\vskip 0.2in
\begin{proof}
We use a proof by induction on $n$.\footnote{You cannot induct on $x$, because $x$ is taken to be a \emph{real} number! So you have to keep $x$ arbitrary throughout this proof - no substituting of $x+1$ for $x$ or anything like that. Make sure you know what your statement $P(n)$ is before you start the induction.} Let $P(n)$ be the sentence
$$P(n):= \forall x>-1, ((1+x)^n \ge 1+nx)$$
\begin{itemize}
\item {\bf Base Case:} $P(1)$ is the statement that, for all $x$, $(1+x)^1 \ge 1+1\cdot x$. The two sides are equal, so the weak inequality $\ge$ holds.
\item {\bf Inductive Step:} Suppose that $\forall x>-1, ((1+x)^n \ge 1+nx)$.

We wish to prove that $\forall x>-1, ((1+x)^{n+1} \ge 1+(n+1)x)$. Let $x$ be an arbitrary real number greater than $-1$. Then
$$\begin{aligned}
(1+x)^{n+1} &= (1+x)^n(1+x) & \\
&\ge (1+nx)(1+x) & \text{(by inductive hypothesis and because }1+x>0)\\
&= 1+nx+x+nx^2 &\\
&= 1+(n+1)x+nx^2 &\\
&\ge 1+(n+1)x & \text{ because }nx^2\ge 0
\end{aligned}$$
We have thus proven $P(n+1)$ and this completes the induction.
\end{itemize}
\end{proof}
\vskip 0.2in
\item [4.] Let $A$ be a finite set of size $n$. Then $|\mathcal{P}(A)|=2^n$.
\vskip 0.2in
\begin{proof}
Let $P(n)$ be the sentence
$$P(n):= \text{ For any set }A\text{ of size }n, |\mathcal{P}(A)|=2^n$$
We prove $\forall n\in\mathbb{N}, P(n)$ by induction on $n$.
\begin{itemize}
\item {\bf Base Case:} Suppose that $A$ is a set of size $1$. Then it has a single element, $x$. Then $A$ has two subsets: $\emptyset$ and $\{x\}$. So $|\mathcal{P}(A)|=2=2^1$, which proves $P(1)$.
\item {\bf Inductive step:} Assume $P(n)$ is true. Now suppose that $A$ is an arbitrary set of size $n+1$. Call its elements $x_1, x_2, \ldots, x_{n+1}$. For any subset $S\subseteq A$, exactly one of $x_{n+1}\notin S$ or $x_{n+1}\in S$ holds true.
\begin{enumerate}
\item In the first case, $S \subseteq \{x_1, \ldots, x_n\}$. By the inductive hypothesis, there are exactly $2^n$ such subsets $S$.
\item In the second case, $S-\{x_{n+1}\} \subseteq \{x_1, \ldots, x_n\}$. By the inductive hypothesis, there are exactly $2^n$ such subsets $S-\{x_{n+1}\}$.
\end{enumerate}
Since the two cases considered are mutually exclusive, the total number of subsets $S\subseteq A$ is $2^n+2^n=2^{n+1}$. Thus $|\mathcal{P}(A)|=2^{n+1}$, which completes the induction.
\end{itemize}
\end{proof}
\vskip 0.2in
\item For all $n\in\mathbb{N}$, $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+\ldots+\frac{1}{n\cdot (n+1)}=\frac{n}{n+1}$. Then use this to prove that
$$\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+\ldots=1$$
\vskip 0.2in
\begin{proof}
Let $P(n)$ be the sentence $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\ldots+\frac{1}{n\cdot (n+1)}=\frac{n}{n+1}$. We prove this by induction on $n$.
\begin{itemize}
\item {\bf Base Case:} For $n=1$, the sentence is $\frac{1}{1\cdot 2}=\frac{1}{1+1}$. This is obvious.
\item {\bf Inductive Step:} Suppose that $P(n)$ holds true. Then
$$\begin{aligned}
\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\ldots+\frac{1}{n(n+1)}+\frac{1}{(n+1)(n+2)} &= \frac{n}{n+1}+\frac{1}{(n+1)(n+2)}\\
&= \frac{n(n+2)+1}{(n+1)(n+2)}\\
&= \frac{n^2+2n+1}{(n+1)(n+2)}\\
&= \frac{(n+1)^2}{(n+1)(n+2)}\\
&= \frac{n+1}{n+2}
\end{aligned}$$
We have proven $P(n+1)$, and so this completes the induction.
\end{itemize}
Now we have proven that $P(n)$ holds true for all $n$. The infinite sum $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\ldots$ can be written as $\sum\limits_{k=1}^{\infty}\frac{1}{k(k+1)}$. And therefore
$$\sum\limits_{k=1}^{\infty}\frac{1}{k(k+1)}=\lim\limits_{n\to \infty}\sum\limits_{k=1}^{n}\frac{1}{k(k+1)}=\lim\limits_{n\to\infty}\frac{n}{n+1}=1$$
\end{proof}
\vskip 0.2in
\item [6.] For all $n\in\mathbb{N}$, $\frac{n(n+1)(n+2)}{1\cdot 2 \cdot 3}$ is an integer. Then show that for all $n\in\mathbb{N}$, $\frac{n(n+1)(n+2)(n+3)}{1\cdot 2\cdot 3\cdot 4}$ is an integer.
\vskip 0.2in
{\bf Note:} The numbers $\frac{n(n+1)}{2}$ are called \emph{triangular numbers} because that number of dots can be arranged into a triangle. The numbers $\frac{n(n+1)(n+2)}{6}$ are called \emph{tetrahedral numbers} for a similar reason.
\begin{proof} [Proof of first assertion]
We prove it by induction on $n$.
\begin{itemize}
\item {\bf Base Case: $n=1$.} This is equivalent to showing that $\frac{1\cdot 2 \cdot 3}{1\cdot 2 \cdot 3}$ is an integer. This is obvious.
\item {\bf Inductive Step:} Suppose that $\frac{n(n+1)(n+2)}{6}$ is an integer. We wish to show that $\frac{(n+1)(n+2)(n+3)}{6}$ is an integer. But
$$\frac{(n+1)(n+2)(n+3)}{6}=\frac{n(n+1)(n+2)}{6}+\frac{3(n+1)(n+2)}{6}=\frac{n(n+1)(n+2)}{6}+\frac{(n+1)(n+2)}{2}$$
and because of Question 1, $\frac{(n+1)(n+2)}{2}$ is an integer. Therefore, $\frac{(n+1)(n+2)(n+3)}{6}$ is an integer, which completes the induction.
\end{itemize}
\end{proof}
\begin{proof} [Proof of section assertion]
Again we prove it by induction on $n$.
\begin{itemize}
\item {\bf Base Case: $n=1$.} This is equivalent to showing that $\frac{1\cdot 2 \cdot 3\cdot 4}{1\cdot 2 \cdot 3\cdot 4}$ is an integer. This is obvious.
\item {\bf Inductive Step:} Suppose that $\frac{n(n+1)(n+2)(n+3)}{24}$ is an integer. We wish to show that $\frac{(n+1)(n+2)(n+3)(n+4)}{4}$ is an integer. But
$$\begin{aligned}
\frac{(n+1)(n+2)(n+3)(n+4)}{24}&=\frac{n(n+1)(n+2)(n+3)}{24}+\frac{4(n+1)(n+2)(n+3)}{24}\\
&=\frac{n(n+1)(n+2)(n+3)}{24}+\frac{(n+1)(n+2)(n+3)}{6}
\end{aligned}$$
and because of the previous assertion, $\frac{(n+1)(n+2)(n+3)}{6}$ is an integer. Therefore, $\frac{(n+1)(n+2)(n+3)(n+4)}{24}$ is an integer, which completes the induction.
\end{itemize}
\end{proof}
{\bf Challenge:} Can you form a more general statement and prove it by induction?
\vskip 0.2in
\item [7.] For all $n\in\mathbb{N}$, $3\mid 2^n+1 \iff 3\nmid 2^n-1$.
\vskip 0.2in
\begin{proof}
Let
$$Q(n) := (3\mid 2^n+1) \land (3 \nmid 2^n-1)$$
$$R(n) := (3\nmid 2^n+1) \land (3\mid 2^n-1)$$
We wish to show $\forall n\in\mathbb{N}, (Q(n) \lor R(n))$. We prove this by induction on $n$.
\begin{itemize}
\item {\bf Base Case:} When $n=1$, $2^n+1=0$ and $2^n-1=2$. Therefore, $R(1)$ is true and $Q(n)$ is false. Thus, $Q(1)\lor R(1)$ is true.
\item {\bf Inductive Step:} We wish to prove $(Q(n) \lor R(n))\implies (Q(n+1) \lor R(n+1))$. This is logically equivalent to showing $Q(n)\implies (Q(n+1) \lor R(n+1))$ and $R(n)\implies (Q(n+1) \lor R(n+1))$. We will show that $Q(n) \implies R(n+1)$ and $R(n)\implies Q(n+1)$, which is sufficient.
\begin{enumerate}
\item Suppose $Q(n)$. Then $3\mid 2^n+1$, so $2^n\equiv -1\pmod{3}$. Then
$$2^{n+1}\equiv -2 \equiv 1\pmod{3}$$
and so $3\mid 2^n-1$ and $3\nmid 2^n+1$. We therefore have $R(n+1)$.
\item Suppose $R(n)$. Then $3\mid 2^n-1$, so $2^n\equiv 1\pmod{3}$. Then
$$2^{n+1}\equiv 2 \equiv -1\pmod{3}$$
and so $3\mid 2^n+1$ and $3\nmid 2^n-1$. We therefore have $Q(n+1)$.
\end{enumerate}
\end{itemize}
\end{proof}
{\bf Note:} Here's a diagram of the logical flow of the last proof.
$$\xymatrix{Q(1)\ar[dr] & Q(2)\ar[dr] & Q(3)\ar[dr] & Q(4)\ar[dr] & \cdots\\
R(1)\ar[ur] & R(2)\ar[ur] & R(3)\ar[ur] & R(4)\ar[ur] & \cdots
}$$
\end{enumerate}
\end{document}