## Most recent change of ProofByInduction

Edit made on May 01, 2009 by GuestEditor at 12:18:35

Deleted text in red / Inserted text in green

WW
HEADERS_END
Proof by induction is a proof made by proving that a statement is true for a general case (i.e. when EQN:n=k ), the next case and the first case; if all three of these are true, then, by induction, the statement must be true.
Proof by induction is a proof made by first assuming that a statement is true for a general case (i.e. when EQN:n=k ), then proving that it still holds true for the next case (i.e. when EQN:n=k+1 ) and then proving that it is true for the first (base) case; if the statement /does/ hold for /both/ the base case /and/ the inductive step ( EQN:n=k+1 ), then, by induction, the statement must be true.

!! METHOD
To prove that something is true for all integers EQN:n{\ge}r , first prove that it is true for EQN:n=k , then prove that it is true for EQN:n=k+1 , and finally prove that it is true for EQN:n=r.
To prove that something is true for all integers EQN:n{\ge}r :
* assume that it is true for EQN:n=k
* prove that it remains true for EQN:n=k+1
* prove that it is true for EQN:n=r.

----

#Hello# #Josh#

case n = k is not proved but assumed.

The proof consists of two steps:
* The basis (base case):
** Show that the statement holds when n = 0 (or n = 1 ...)
* The inductive step:
** show that if the statement holds for some n, then the statement also holds when n + 1 is substituted for n.

Hope this helps
!! Examples
It would be nice to have some small, clean examples here. Not too many, not too much.