Simple induction Proof
-------------------------

Claim: The sum of the first n odd numbers is equal to n^2

Base case (n=1): the sum of the 1 odd numbers is just 1 = 1^2

Inductive step: Assume the claim is true for n.  We wish to prove the claim for n+1:
From the induction hypothesis, we know that the sum of the first n numbers is n^2.
We also know the (n+1)th odd number is equal to 2n+1.  So the sum of the first n+1 odd
numbers is n^2 + 2n + 1 = (n+1)^2.  Thus, proving the claim for n+1.

Therefore, by induction, the claim is true for all n >= 1.

-------------------------------------------------------------------------------------------
A more mathematical way
-------------------------------------------------------------------------------------------

Claim: From i = 1 to n, sum(2i-1) = n^2 (it's the same claim)

Base case (n=1): sum(1) = 1 = 1^2

Inductive step: Assume the claim is true for n.  We wish to prove the claim for n+1:
From i=1 to n+1, sum(2i-1) = From i=1 to n, sum(2i-1) + 2(n+1)-1
			   = n^2 + 2(n+1) - 1    <--Induction hypothesis
			   = n^2 + 2n + 1
			   = (n+1)^2

Therefore, by induction, the claim is true for all n >= 1.

-------------------------------------------------------------------------------------------
Tricky Induction proof
-------------------------------------------------------------------------------------------

Claim: All people in the world are the same height.

Base case (n=1): If there is one person in this world, then it is trivial that all the
people in the world are of the same height.

Inductive step: Assume the claim is true for n.  We wish to prove the claim for n+1.
Let the set of all people in the world be W, where |W| = n+1.  Divide the set W into sets
A and B such that |A| = |B| = n and W = A U B (see InductionEx.jpg).  From the induction 
hypothesis, we know that all the people in set A are of the same height, and all the people 
in B are of the same height.  Let x be an element of both A and B.  Since all the elements 
in A are the same height as x and all the elements in B are the same height as x, all the 
people in A U B = W are the same height.  Therefore, by induction, the claim is true for all
n >= 1.

Obviously this claim is false... so what's wrong with this proof?!?!

Answer: The statement "Let x be an element of both A and B" is a bad assumption.  In
general, for n >= 3, there will be such an element that exists in both A and B, but
consider the case n = 2.  For this case, both A and B each have one element because
W = A U B, but then there is no common element between A and B.  Therefore, "our
assumption "Let x be an element of both A and B" is incorrect because x does not
necessarily exist (see bottom picture of InductionEx.jpg).