\documentclass[12pt, letterpaper]{article}
\usepackage{fullpage}
\usepackage{graphics}
\usepackage{amssymb}

\title{TJ USAMO Practice 4- Induction}
\author{PDiao05}
\date{\today}
\begin{document}

\maketitle

\section{So what is induction anyways?}

\par It turns out that induction comes hand in hand with the Well Ordering Principle. 
In fact the two can be proven from each other so they are equivalent statements.  That was useless gibberish
unless you want to later on ask me or look up what WOP actually is.  Anyways, all induction asserts is that the truth of
an infinite sequence of propositions $P_i$ for $i = 1,2, \cdots, \infty$ is established if the following two are satsfied:

\begin{enumerate}
\item $P_1$ is true, this is called the \textbf{base case},
\item $P_k$ (\textbf{inductive hypothesis}) true $\Rightarrow P_{k+1}$ true for all $k$.
\end{enumerate}

\par This calls for a concrete example!  Most of you are probably familiar with the following formula:
$$\sum_{k=1}^{n} k = \frac{(n)(n+1)}{2}$$
You can prove this formula several ways but here I present a simple inductive proof.
First we define what ``proposition i" means.  $P_i$ states that:
$$\sum_{k=1}^{i} k = \frac{(i)(i+1)}{2}$$
That is all.  It basically states that what we are trying to prove is true when $n=i$.  
In fact since we are setting $n=i$ the ith proposition is basically the nth proposition.  This is 
often referred to as ``inducting on n". Now we have to figure out a way of satisfying our two
requirements:

\begin{enumerate}
\item We want to show that $P_1$ is true.  This means we need to show that:
$$\sum_{k=1}^{1} k = \frac{(1)(1+1)}{2}$$
But this is true by straight up evaluation.  Yay our \textbf{base case} is done.
\item We now want show that based on our \textbf{inductive hypothesis} that $P_n$
is true we can conclude that $P_{n+1}$ is true.  Our inductive hypothesis is:
$$\sum_{k=1}^{n} k = \frac{(n)(n+1)}{2}$$
Given that, we can add $n=1$ to both sides of the expression and rearrange some:
$$n + 1 + \sum_{k=1}^{n} k = \frac{(n)(n+1)}{2} + n + 1$$
$$\sum_{k=1}^{n+1} k = (\frac{n}{2}+ 1)(n+1)$$
$$\sum_{k=1}^{n+1} k = \frac{(n+2)(n+1)}{2}$$
Whoa, we've stumbled upon $P_{n+1}$.  Now that we have proven the base case and the inductive step
we can declare the induction complete.  In fact you should make such a statement at the end of inductions
just to be clear.
\end{enumerate}

\section{Practice}

\begin{enumerate}
\item Prove with induction that: 
$$\sum_{k=1}^{n} k^2 = \frac{(n)(n+1)(2n+1)}{6}$$
\item Prove the Binomial Theorom:
$$(x+y)^n = \sum_{k=0}^{n} {n\choose k}x^{k}y^{n-k}$$
\item (MOSP 2005) Let $a_0, a_1, \cdots a_n$ be integers, not all zero, and all at least -1.  Given 
$a_0 + 2a_1 + 2^{2}a_2 + \cdots + 2^{n}a_n = 0$, prove that $a_0 + \cdots + a_n > 0$.
\item How many sections of the plane can we divide it into with $n$ lines?
\end{enumerate}

\section{Strong Induction and WOP}

\par I guess I lied a little earlier.  In reality there is a type of induction called strong induction.  This
type of induction most clearly mirrors WOP.  Here are the statements of these two things:
\begin{itemize}
\item \textbf{Strong Induction}: Prove $P_1$ and that if $P_1, P_2,
\dots, P_n$ are all true, then $P_{n+1}$ is also true.
\item \textbf{Well Ordering Principle}: Take the smallest $n$ such
that $P_n$ is false. Then show that, for some $k < n$, $P_k$ is
false (which could require proving a base case). This is a
contradiction, so $P_n$ is true for all $n$.
\end{itemize}

\section{More Practice}
\begin{enumerate}
\item Prove that $\sqrt{3}$ is irrational.
\item (MOSP 2005) This one is kinda hard and induction (of the non-strong variety) isn't the only way to do it.  If somebody solves it I
might even tell a story about it.  Show that for nonnegative integers $m$ and $n$:
$$\sum_{j = 0}^{m} (-1)^{j}\frac{{m\choose j}}{n+j+1} = \sum_{k = 0}^{n} (-1)^{k}\frac{{n\choose k}}{m+k+1}$$
\end{enumerate}
\end{document}