From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU  Wed Mar 19 19:51:39 2008
Date:         Wed, 19 Mar 2008 19:51:17 -0400
From: "William J. Rapaport" <rapaport@cse.Buffalo.EDU>
Subject: 191 Proof by Mathematical Induction
To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU

------------------------------------------------------------------------
Subject: 191 Proof by Mathematical Induction
------------------------------------------------------------------------

Here's another example of a proof by mathematical induction.

------------------------------------------------------------------------
Notation:  I'll use:
		 "\in" for the set-membership symbol;
		 "b1", "b2",..., for "b" subscripted with 1,2,...;
		 "b_n", "b_k", "b_(k+1)" for "b" subscripted with "n",
					     or with "k", or with "k+1";
		 "A" for the universal quantifier;
		 "SIGMA" for the summation symbol;
		 ">=" for "greater than or equal to"

and recall from a previous posting that when I write something like:

	SIGMA(i \in {1,...,n})

that's just another way of writing the SIGMA with "i=1" underneath it
and with "n" or with "i=n" on top of it, as on pp. 153ff.	
------------------------------------------------------------------------

Theorem (General Distributive Law):
-----------------------------------

	Let a,b \in R = {x| x is a real number}
	Then, for any natural number n,
		a*(b1+...+b_n) = a*b1+...+a*b_n

proof by induction:
-------------------

First, it will be helpful to re-state the theorem in FOPL:

	(A n \in N)[a*(b1 + ... + b_n) = a*b1 + ... + a*b_n]

Note:  Using the SIGMA notation, we need to show:

	An[a*SIGMA(i \in {1,...,n})[b_i] = SIGMA(i \in {1,...,n}[a*b_i]

So, for the mathematical induction,

	P(n) is: a*(b1+...+b_n) = a*b1+...+a*b_n

base case, first (failed) attempt:
	Show P(0):
	Hmmm, what on earth could P(0) be??  
	I have no idea, but math inductions can begin with 1,

	so let's re-state the theorem as: (A n >= 1)P(n)

...base case, second (slightly more successful) attempt: 
	Show P(1):
	i.e., show a*b1 = a*b1.  That's trivially true!  Easy!

	There's only one problem:  It won't be of any help to us :-|

	So let's re-state the theorem one more time as:

		(A n >= 2)P(n)

	(This is the only interesting case anyway.)

...base case, third (successful) attempt:
	Show P(2):
	i.e., show a*(b1+b2) = a*b1 + a*b2:
		Almost trivial(!), because...
		...this **is** the distributive law of multiplication
		over addition, which is an axiom.

	So now we're ready for the...

...inductive case:	
	Show Ak[P(k) -> P(k+1)]:

	i.e., show Ak[a*(b1+...+b_k) = a*b1 + ... + a*b_k

			->

	              a*(b1+...+b_(k+1)) = a*b1 + ... + a*b_(k+1)]

	To do this, we'll suppose a*(b1+...+b_k) = a*b1 + ... + a*b_k

		(that's the "inductive hypothesis")

	& show a*(b1+...+b_(k+1)) = a*b1 + ... + a*b_(k+1)

	Now comes the "hard" part:   Let's compute a*(b1+...+b_(k+1)):

	a*(b1+...+b_(k+1)) = a*(b1 + ... + b_k + b_(k+1))
				(just spelling out the "...")

	                   = a*( (b1 + ... + b_k) + b_(k+1))
				(just putting some parentheses in)

	                   = a*(        B         + b_(k+1))
				( just letting B = (b1 + ... + b_k) )
	
	                   = a*B + a*b_(k+1), by the base case!

	                   = a*(b1 + ... + b_k) + a*b_(k+1)
				(by the definition of B)

	                   = (a*b1 + ... + a*b_k) + a*b_(k+1)
				(by the inductive hypothesis)

QED