\problemdata                                                             
        {Sum of Odd numbers formula} % latex-friendly label for the prob.
        {Induction} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Quiz1, 2} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Prove {\bf by induction} (other methods will not receive credit) that
\[
1 + 3 + 5 + \cdots + (2n-1) = n^2
\]
for all natural numbers $n \geq 1$.

\solution{
Let $P(n)$ be $1 + 3 + 5 + \cdots + (2n-1) = n^2$.
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove $\forall n \in N, P(n)$  (by induction on n).\\
1. (Base) $n=1$: $2\cdot1-1=1=1^2$\\
2. (Inductive Step)  $\forall n \geq 0 (P(n) \Rightarrow P(n+1))$ \\
\> 1. Fix $n \geq 0$. \\
\> 2. Assume $1 + 3 + 5 + \cdots + (2n-1) = n^2$ \\
\> 3. $1 + 3 + 5 + \cdots + (2(n+1)-1) = (n+1)^2$ \\
\> \> 1. $1 + 3 + 5 + \cdots + (2(n+1)-1) =$  \\
\> \> \> $(1 + 3 + 5 + \cdots + (2n-1)) + (2n+1)$  \> \> Sum with extra term,\\
\> \> \> \> \> Associativity of addition \\ 
\> \> 2. $1 + 3 + 5 + \cdots + (2(n+1)-1) = n^2 + (2n+1)$ \> \> \> Inductive
hypothesis $P(n)$, (2.2.1)\\ 
\> \> 3. $1 + 3 + 5 + \cdots + (2(n+1)-1) = (n+1)^2$ \> \> \> Algebra\\
\> 4. QED \> \> \> \> Implication, UG \\
3. QED  \> \> \> \> \> Induction 
\end{tabbing}

A minority of students treated $P(n)$ as an algebraic expression
rather than a boolean one.  They asserted statements of the form:
$P(n) + (2n+1) = P(n+1)$.  These collections of symbols got little credit.
}

\end{problem}                    