\documentclass{article}
\usepackage{amsmath}
\usepackage{amsthm}

\newtheorem{thm}{Theorem}

\title{Proof by Induction}
\author{Doug Baldwin}
\date{Spring 2021}


\begin{document}

\maketitle

Here are some examples of proofs by induction.

The first is about sums of even numbers. Proofs about sums of infinite sets of natural numbers lend themselves well to proof by induction. 

\begin{thm}
For all natural numbers $n$,
\begin{equation}
\label{sumEqn}
\sum_{i=1}^n 2i = n(n+1)
\end{equation}
\end{thm}

\begin{proof}
We will prove that equation (\ref{sumEqn}) holds for all natural numbers by induction.

For the basis step we consider $n = 1$. Then
\begin{align*}
\sum_{i=1}^n 2i &= \sum_{i=1}^1 2i \\
&= 2 \\
&= 1(1+1)
\end{align*}
So we have established that Equation (\ref{sumEqn}) holds when $n=1$.

We now turn to the induction step. We assume
\begin{equation*}
\sum_{i=1}^k 2i = k(k+1)
\end{equation*}
for some natural number $k \ge 1$.  We then show that Equation (\ref{sumEqn}) holds for $k+1$ as follows:
\begin{align*}
\sum_{i=1}^{k+1} 2i &= \sum_{i=1}^{k} 2i + 2(k+1) \\
&= k(k+1) + 2(k+1) \\
&= (k+1)(k+2)  \\
&= (k+1)(k+1+1)
\end{align*}

Since we have now proved that Equation (\ref{sumEqn}) holds for $n=1$ and that if it holds for $n=k$ it also holds for $n=k+1$, we have shown by induction that  for all natural numbers $n$
\begin{equation*}
\sum_{i=1}^n 2i = n(n+1)
\end{equation*}
\end{proof}

\end{document}
