%====================================================================
% This is a LaTeX-2e document
%====================================================================

%\documentclass[12pt]{amsart}
\documentclass[10pt]{article}
\parindent=0pt \parskip=8pt

\usepackage{verbatim}
\usepackage{fullpage}

\usepackage{amssymb,amsmath,amsthm}
\usepackage[mathscr]{eucal}

\usepackage{makeidx}
\input{../tex/isomath}
\input{../tex/mathenv}

\newcommand{\qand}{\quad\textrm{and}\quad}
\newcommand{\qqand}{\qquad\textrm{and}\qquad}

%--------------------------------------------------------------------
\begin{document}
\title{Induction and the sum of consecutive squares}
\author{John Kerl $\cdot$ Math 110, section 2 $\cdot$ Spring 2006}
%\date{\today}
\date{}
\maketitle

In chapter 5 we encountered formulas for the sum of consecutive integers and
the sum of consecutive squares:
$$
	\sum_{k=1}^n k   = \frac{n(n+1)}{2}
	\qqand
	\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}.
$$
For example,
$$
	1+2+3+4+5 = \frac{5\cdot 6}{2} = 15
	\qqand
	1+4+9+16+25 = \frac{5\cdot 6 \cdot 11}{6} = 55.
$$
But this story has a significant omission:  Why are these true --- are we just
supposed to accept these formulas on faith?  Does trying the formula out for a
few values of $n$ convince you it's true for \emph{every} $n$?  This question
is answered easily enough, using a technique called \emph{induction}.  This
technique could be taught in college algebra (maybe at some universities it
is), and it's useful throughout mathematics.

%% ----------------------------------------------------------------
\section{Induction}

The idea of an inductive proof is as follows:  Suppose you want to show that
something is true for all positive integers $n$.  (The catch:  you have to
already know what you want to prove --- induction can prove a formula is true,
but it won't produce a formula you haven't already guessed at.)

\begin{itemize}
\item \textbf{Step 0.} Come up with a formula, and give yourself reason to
think it's true.
\item \textbf{Step 1} (\emph{base case}). Show the formula holds for $n=1$.
\item \textbf{Step 2} (\emph{induction step}).  \emph{Suppose} it's true for
	$n-1$, and then \emph{show} it's true for $n$.
\end{itemize}

This is a leapfrog type of argument.  It's kind of like evaluating the terms of
a sequence:  you have a starting point, and you get the next term by doing
something to the previous term.  This chains along for as long as you have
patience.

I showed in class (and your textbook also shows) why the first formula above,
the sum-of-consecutive-integers formula, is true.  (It's an arithmetic sum.) So
we \emph{could} use induction for that formula, but we don't \emph{need} to.
I'll illustrate the induction technique by proving that the
sum-of-consecutive-squares formula is true.

%% ----------------------------------------------------------------
\section{Sum of consecutive squares}

Let's see why
$$
	\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}.
$$

\textbf{Step 0.} How do we come up with the formula?  In this case, it comes
from your instructor and/or textbook authors.  Does it look like it's true?  We
can try a few values of $n$.  We did this in class, and above we had
$$
	1+4+9+16+25 = \frac{5\cdot 6 \cdot 11}{6} = 55.
$$
The formula claims that the sum \emph{should} be 55, and when we add up the
terms, we see it \emph{is} 55.

\textbf{Step 1.} (\emph{Base case}) Show the formula holds for $n=1$.  This is
usually the easy part of an induction proof.  Here, this is just
$$
	\sum_{k=1}^1 k^2 = 1^2 = \frac{1 (1+1) (2\cdot1 + 1)}{6}
	= \frac{1\cdot 2 \cdot 3}{6}
	= 1.
$$

\textbf{Step 2.} (\emph{Induction step})  \emph{Suppose} it's true for $n-1$,
and then \emph{show} it's true for $n$.  For this part, you usually need to do
some algebraic manipulation.  First we write down the expression for the sum of
$n$ consecutive squares:
$$
	\sum_{k=1}^n k^2.
$$
We're pretending we don't know that this is $n(n+1)(2n+1)/6$, so we don't give
ourselves permission to write that down yet.  Our job is to come up with that
as a \emph{consequence} of what we \emph{are} sure of, namely, that it's true
for $n-1$.

The trick is that this is just the sum of $n$ numbers, so we can split it up
into the sum of the first $n-1$ terms, and the very last term all by itself:
$$
	\sum_{k=1}^n k^2
	= \sum_{k=1}^{n-1} k^2 + \sum_{k=n}^n k^2 
	= \sum_{k=1}^{n-1} k^2 + n^2.
$$
Now, we're pretending we \emph{are} confident of what the sum of the first
$n-1$ consecutive squares is, so we can write this as:
\begin{eqnarray*}
	\sum_{k=1}^n k^2
	=
	\sum_{k=1}^{n-1} k^2 + n^2
	&=& \frac{(n-1)[(n-1)+1][2(n-1)+1]}{6} + n^2 \\
	&=& \frac{(n-1)(n)(2n-1)}{6} + n^2.
\end{eqnarray*}
We need to turn this into what we want, which is
$$
	\frac{n(n+1)(2n+1)}{6}.
$$
The question then reduces to:
$$
	\frac{(n-1)(n)(2n-1)}{6} + n^2
	\quad
	\stackrel{?}{=}
	\quad
	\frac{n(n+1)(2n+1)}{6}.
$$
All we need to do is FOIL these out and simplify.  Since the right-hand side
has one big denominator of 6, maybe we could put the left-hand side into the
same form.

The left-hand side is
\begin{eqnarray*}
	\frac{(n-1)(n)(2n-1)}{6} + n^2
	&=&
	\frac{(n-1)(n)(2n-1) + 6 n^2}{6}
\end{eqnarray*}
which FOILs out to
\begin{eqnarray*}
	\frac{(n^2-n)(2n-1) + 6n^2}{6}
	&=& \frac{2n^3 - n^2 - 2n^2 + n + 6n^2}{6} \\
	&=& \frac{2n^3 + 3n^2 + n}{6}.
\end{eqnarray*}

The right-hand side FOILs out to
\begin{eqnarray*}
	\frac{n(n+1)(2n+1)}{6}
	&=& \frac{(n^2+n)(2n+1)}{6} \\
	&=& \frac{2n^3 + n^2 + 2n^2 + n}{6} \\
	&=& \frac{2n^3 + 3n^2 + n}{6} \\
\end{eqnarray*}
which is the same thing as the left-hand side.

In summary, we showed that the formula is true for $n=1$.  Then we showed that
\emph{if} the sum-of-consecutive-squares formula is true for an integer,
\emph{then} it's also true for the next integer.  Since it's true for $n=1$
(the base case), it's true for $n=2$ by the induction step.  Since it's true
for $n=2$, it's true for $n=3$ by the induction step, and so on.  Then we are
sure that it's true for any $n$ at all.

%% ----------------------------------------------------------------
\section{Two questions}

Since we have formulas for the sum of consecutive \emph{integers} and the sum
of consecutive \emph{squares}, it's natural to wonder: what do you get when you
sum up consecutive \emph{cubes}?  For example,
\begin{eqnarray*}
	1 &=& 1 \\
	1+8 &=& 9 \\
	1+8+27 &=& 36 \\
	&\vdots&
\end{eqnarray*}

Here's another one --- the sum of consecutive \emph{odd} integers:
\begin{eqnarray*}
	1 &=& 1 \\
	1+3 &=& 4 \\
	1+3+5 &=& 9 \\
	&\vdots&
\end{eqnarray*}

For either of these: Do you see a pattern?  Can you guess a formula?  Can you
convince yourself it's probably true?  Can you prove it's true?

%% ----------------------------------------------------------------
\section{More information}

There's a nice write-up on \emph{Mathematical induction} in Wikipedia, at
\texttt{http://en.wikipedia.org}.

\end{document}
