mathematical_induction.tex

\yourname

\activitytitle{Mathematical Induction}{Proving that a claim is true for all $n=1, 2, 3, \ldots$ by building on previous results.  }

\overview{One important task in mathematics is to find regular patterns and prove that they hold.
The main method we use for this is mathematical induction.
This activity was co-authored by Ying-Ju Chen.}

\theorem{\bf Mathematical induction\label{MItheorem}}\\
{For each integer $n=1, 2, 3, \ldots$, let $P(n)$ denote a true/false logical statement involving $n$.
\begin{itemize}
\item[(i)] (The basis step) Prove that $P(1)$ is true.
\item[(ii)] (The inductive step) For each $n = 1, 2, 3, \ldots$, suppose that $P(n)$ is true, and use $P(n)$ to prove that $P(n+1)$ is true.
\end{itemize}
From the above two steps, we can conclude that $P(n)$ is true for all $n = 1, 2, 3, \ldots$.}

\note{Proving the inductive step is usually done as a ``rewrite'' proof, where you start with the left hand side of what you want to show and rewrite until you come to the desired right hand side.
Often, some quantity in the statement $P(n+1)$ can be written in terms of a similar quantity in the statement $P(n)$ plus a new part.
You will always use the fact that $P(n)$ is true.}

\question{With induction proofs, $P(n)$ is always a true/false logical statement.
A student working on an induction problem wrote $P(n+1) = P(n) + \frac{1}{n^2}$.
How can you tell that this must be wrong?}
{0.2in}

\guidedproof{\label{inductionguidedproof}
Use mathematical induction to show that $3^n$ is odd for all $n = 1, 2, 3, \ldots$.
\balist{0.0in}
\item State $P(n)$:  $P(n)$ is that ``\blank{2in}''
\item Basis step:  $P(1)$ is that ``\blank{1.5in}.''  This is true because \blank{1.5in}.
\item State $P(n+1)$:  $P(n+1)$ is that ``\blank{2in}''
\item Inductive step:  Let $n \geq 1$.  suppose that $P(n)$ is true.  Show that $P(n+1)$ is true.
You may use facts you have already proven about odd numbers.

\noindent
Because $P(n)$ is true, \blank{1.5in}.
Now $3^{n+1}=$ \blank{1in}, which is odd because \blank{4.5in}.
Thus $P(n+1)$ is true.
Since $n \geq 1$ was arbitrary, by mathematical induction, $P(n)$ is true for all $n \geq 1$.
\elist
}

\exercise{Fill in the table using your powers of pattern recognition.

\vspace*{0.1in}
\label{examplesum}
\centerline{
\begin{tabular}[c]{c|c|c|c|c|c|c|c|c|c|c}
  $k$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & $\cdots$ & $n$ & $n+1$ \\
  \hline
  $k$th odd integer & 1 & 3 & 5 & 7 & & & & $\cdots$ & & \\
  \hline
  sum of first $k$ odd integers & ~1~ & ~4~ & \hspace{0.2in} & \hspace{0.2in} & \hspace{0.2in} & \hspace{0.2in} & \hspace{0.2in} & $\cdots$ & \hspace{0.5in} & \hspace{0.5in} \\
\end{tabular}}

\vspace*{0.1in}
\noindent
Column $n$ of the table contains a conjecture about the sum of the first $n$ odd integers.
In the next problem, you will use mathematical induction to prove it.
}{0.0in}

\pagebreak
\guidedproof{\label{oddsum}
Prove the conjecture in \ref{examplesum} using mathematical induction.
\balist{0.05in}
\item State $P(n)$:  $P(n)$ is that ``the sum of the first $n$ odd integers equals \blank{1in}''
\item Basis step:  $P(1)$ is that the sum of the 1st odd integer is $1^2.$  
This is true because the sum is 1 and because $1^2 = 1$.
\item Write out $P(n+1)$:  $P(n+1)$ is that ``the sum of the first \blank{3in}''
\item Inductive step: Let $n \geq 1$.  suppose that $P(n)$ is true, and use that to show that $P(n+1)$ is true.
\begin{eqnarray*}
\lefteqn{\mbox{the sum of the first $n+1$ odd integers}} \\
&=& \mbox{the sum of the first $n$ odd integers plus \blank{1in}} \\
&=& \blank{1.5in} + \blank{1.5in} \mbox{since $P(n)$ is true} \\
&=& \blank{1.5in} \mbox{by algebra}
\end{eqnarray*}
Thus $P(n+1)$ is true.
Since \blank{1in} was arbitrary, by \blank{2in} we conclude that the sum of the first $n$ odd integers equals \blank{1in} for all $n = 1, 2, 3, \ldots$.
\elist
}

\notation{Summation notation for $a_1+a_2+a_3+\cdots+a_n$ is $\displaystyle \sum_{k=1}^{n}a_k$.
For example, $\displaystyle \sum_{k=1}^{n} k = 1 + 2 + \cdots + n$.}

\example{Use summation notation and the formula for the $n$th odd integer in \ref{examplesum} to rewrite $P(n)$ in \ref{oddsum}:
$P(n)$ is that \blank{1.5in} = \blank{0.5in}}{0in}

\exercise{Fill in the blanks to practice splitting off the last term of a sum.

{\bf a.} $\displaystyle \sum_{k=1}^{n+1} k^2 = \left( \sum_{k=1}^{n} k^2 \right) + \blank{1in}$
\qqqq
{\bf b.} $\displaystyle \sum_{k=1}^{n+1} \frac{1}{k^3} = \left( \sum_{k=1}^{n} \frac{1}{k^3} \right) + \blank{1in}$
}{-0.1in}

\show{Show that $\sum_{k=1}^n 4k-3 = n(2n-1)$ for all $n = 1, 2, 3, \ldots$.
\balist{0.0in}
\item State $P(n)$:  $P(n)$ is that
\item Basis step:  $P(1)$ is that  \hfill This is true because: \blank{1.5in}
\item State $P(n+1)$:  $P(n+1)$ is that

\vspace*{0.2in}
\noindent
Suggestion:  Use algebra to simplify the right hand side.

\item Inductive step: Let $n \geq 1$.  suppose that $P(n)$ is true, and use that to show that $P(n+1)$ is true.

\vspace*{-0.2in}
\begin{eqnarray*}
\sum_{k=1}^{n+1} 4k-3 &=& \sum_{k=1}^{n} \blank{1.5in} + \blank{1.5in} \\
                                         &=& \blank{1.5in} + \blank{1.5in} \qq \mbox{since $P(n)$ is true} \\
                                         &=& \\
                                         &=& 
\end{eqnarray*}
Thus, \blank{1.5in}.  Since ... 
\elist
}{0.0in}

\stop{Compare your proofs with the other people in your group before you move on.}

\show{Use mathematical induction to show that $\sum_{k=1}^n 5^k = \frac{5}{4} (5^n-1)$ for all integers $n = 1, 2, 3, \ldots $.
\balist{0.1in}
\item State $P(n)$:  
\item Basis step:  
\item State $P(n+1)$:  

\vspace*{0.2in}
\noindent
Suggestion:  Multiply out the right hand side.

\item Inductive step: Let $n \geq 1$.  suppose that $P(n)$ is true, and use that to show that $P(n+1)$ is true.
\elist
}{1.1in}

\note{The basis step need not use $n=1$, for example, it can use $n=-3, n= 0,$ or $n = 100$.}

\show{Use mathematical induction to show that $2n+1 < 2^n$ for all integers $n$ with $n \geq 4$.
\balist{0.10in}
\item State $P(n)$:
\item Basis step:  $P(4)$ is that:  \hfill Check: \blank{1.5in}
\item State $P(n+1)$:  
\item Inductive step: Let $n \geq 4$.  suppose that $P(n)$ is true, and use that to show that $P(n+1)$ is true.
\begin{eqnarray*}
2(n+1) + 1 = \blank{1.5in} &=& \blank{1.5in} \\
                                            &<& \blank{1.5in} \qq \mbox{since $P(n)$ is true}\\
                                            &<& 2^n + 2^n \qq \mbox{since \blank{1in}}\\
                                            &=& 2^{n+1}.
\end{eqnarray*}
Thus, \blank{1.5in}.  Since ... 
\elist
}{0in}

\show{Use mathematical induction to show that $5^n > 2^n + 3^n$ for all integers $n$ with $n \geq 2$.  Use the same format as above.
\balist{0.1in}
\item
\item
\item
\item
\elist
}{0.0in}

% ====================================================
\pagebreak

\show{Use induction to prove Bernoulli's inequality: For all $x\in \R$, if $1+x >0$, then $(1+x)^n \geq 1+nx$ for all $n = 0, 1, 2, \ldots$.  Use the same format as above.

\noindent
Let $x$ be such that $1+x > 0$.

\vspace*{1.5in}
\noindent
Where did you use the assumption that $1+x > 0$?
}{0in}

\show{Use induction to prove that $\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \frac{1}{3\cdot 4} + \cdots+\frac{1}{n\cdot (n+1)} = \frac{n}{n+1}$ for all positive integers $n$. \label{sumeq}
Start by writing $P(n)$ using summation notation.
}{1.5in}

\note{It is possible to show that the statement in \ref{sumeq} is true without using mathematical induction, but using an algebraic technique.  How?}

\show{For each $n\in \Z^+$, let $P(n)$ denote the statement ``$n^2+5n+1$ is an even integer.''
\balist{0.05in}
\item State $P(n+1)$
\item Suppose that $P(n)$ is true, and use that to prove that $P(n+1)$ is true.
\vspace*{0.5in}
\item For which $n$ is $P(n)$ actually true? 
\item What is moral of this exercise?
\elist
}{0in}

\show{Use induction to prove that $n^3-n$ is a multiple of 6 for all integers $n = 0, 1, 2, \ldots$.
Do the induction step as a ``rewrite'' proof.}{1.5in}

\show{Use induction to prove that $11^n-4^n$ is a multiple of 7 for all $n = 0, 1, 2, \ldots$.
Do the induction step as a ``rewrite'' proof.
\Hint Use the equation $11^n-4^n = 7k$ once.}{1.3in}

\example{Write the following numbers as multiples of 5 plus a remainder from 0 to 4.

37 = 5 $\cdot$ \blank{0.5in} + \blank{0.5in}

38 = 5 $\cdot$ \blank{0.5in} + \blank{0.5in}

39 = 5 $\cdot$ \blank{0.5in} + \blank{0.5in}

40 = 5 $\cdot$ \blank{0.5in} + \blank{0.5in}

41 = 5 $\cdot$ \blank{0.5in} + \blank{0.5in}

}{-0.2in}

\prove{Let $k > 0$ be an integer.
For each integer $n$, let $P(n)$ be the statement: ``There exist integers $q$ and $r$ with $0 \leq r < k$ such that $n = kq + r$.''
Use mathematical induction to show that $P(n)$ is true for all integers $n$.

\balist{0.4in}
\item Show that $P(0)$ is true.

\item Let $n$ be an integer.
Suppose that $P(n)$ is true, so that $n = kq+r$ for some integers $q$ and $r$, with $0 \leq r < k$.
Show that there exist integers $q'$ and $r'$ with $0 \leq r' < k$ so that $n+1 = kq' + r'$, and thus conclude that $P(n+1)$ is true.
Note that you will define $q'$ and $r'$ in terms of $q$ and $r$.
It is helpful to do this with two cases, depending on the value of $r$:

\noindent
Case 1.  Suppose $0 \leq r < k-1$.

\vspace*{0.5in}

\noindent
Case 2.  Suppose $r = k-1$.

\item Suppose that $P(n)$ is true and show that $P(n-1)$ is true.
It is helpful to do this with two cases.
\elist

\vspace*{1in}
\noindent
Use steps b and c and the idea of mathematical induction to conclude the proof that $P(n)$ is true for all $n$.

}{0in}

% ================================================================
\pagebreak

\show{
Use mathematical induction to prove that $\displaystyle \sum_{k=1}^{n} k = \frac{1}{2}n(n+1)$ for all integers $n = 1, 2, 3, \ldots$.
}{1.1in}

\show{
Use mathematical induction to prove that $\displaystyle \sum_{k=1}^{n} k^2 = \frac{1}{6}n(n+1)(2n+1)$ for all integers $n = 1, 2, 3, \ldots$.
}{1.1in}

\show{Let $r$ be a real number not equal to 1.
Use induction to prove that $\displaystyle \sum_{k=0}^{n} r^k = \frac{1-r^{n+1}}{1-r}$ for all integers $n = 0, 1, 2, \ldots$.
Note where you use the assumption on $r$.
}{1.1in}

\show{Use mathematical induction to show that $n! > 3^n$ for all $n = 7, 8, 9, \ldots$.}{1.4in}

\show{For $n = 2, 3, \ldots,$ let $P(n)$ be the statement ``$n$ is prime or $n$ can be written as the product of prime factors less than $n$.
Supposing that $P(2), P(3), \ldots, P(n)$ are true, show that $P(n+1)$ is true, and thus conclude that $P(n)$ is true for all $n = 2, 3, \ldots$.
This is called {\em strong induction}.
}{1.1in}

\show{Prove that $1^2-2^2+3^2-4^2+5^2+\cdots-(2n)^2+(2n+1)^2 = (n+1)(2n+1)$ for all $n = 0, 1, 2, \ldots$. 
Start by writing $P(n)$ using summation notation, starting from $k=0$.}{0in}

\vfill          % pad the rest of the page with white space