September 8


* Proof By Induction

  How do we prove something is true about a finite set?
  Show it is true for each element.

  How do we prove something is true about an infinite set?
  One method is to use proof by induction.

  1.  Show that the property applies to one specific member of the
      set (Base Case)
  2.  Show that IF the property holds for N members of the set
      (Inductive Hypothesis), then
  3.  The property MUST hold for N+1 members of the set
      (Inductive Step)


   If we can prove the base case and the inductive step, then we could apply the
inductive step first to the base case producing the next case (now true for
2 instances), then apply it again (now true for 3 instances), and so on, to show
the property holds for each element of the set.

   Inductive proofs are often used to prove properties hold for infinitely
large sets.

   - Example
     Prove that for any n>=0 (n in N),
	sum_{x=1}^{n} x = (n+1)n / 2.

     1) Base case
	Let n = 0.  The sum on the left side is 0, the expression on the right
	   is 1*0 / 2 = 0.
	   Can prove similarly for n=1, n=2
	   n=2
	   1 + 2 = 2*3 / 2, so the property holds

     2) Inductive hypothesis
	Assume the property is true for n=k.

     3) Inductive Step (if true for n=k, is it then true for n=k+1?)
	The left side is
	   1 + 2 + 3 + ... + k + k+1, or

	   (sum_{x=1}{k} x) + k+1

	   Plugging in the formula we know to be true for n=k, we get
	   the left hand side = ((k+1)k / 2) + k+1, which equals
	   (k+1)k + 2(k+1)      k^2 + 3k + 2   (k+2)(k+1)
	   ---------------   =  ------------ = ----------,
		  2                   2            2

	   which is the right hand side of the equation for n=k+1.
	   Thus the property holds.


   - Example
     Prove that for any n>=0 (n in N),
	sum_{i=1}{n} i^2 = n(n+1)(2n+1)
			   ------------.
				6

     1) Base case.  Let n=0, left side = 0, right side = 0, property holds.
     2) Inductive hypothesis.  True for n-1 (another way of rephrasing the
	same approach).
     3) Inductive Step.  Is it then true for n?
	Left side = (n-1)n(2n-1)         (n^2 - n)(2n-2)
		    ------------ + n^2 = ---------------
			 6                      6

	  2n^3 - 2n^2 - 2n^2 + 2n + 6n^2    2n^3 + 3n^2 + 2n   n(n+1)(2n+1)
	= ------------------------------ = ----------------- = ------------
		       6                         6                 6

	Thus the property holds.


* Pigeonhole Principle

   Example:  If you have a drawer full of black and white socks, how many
   socks must you select before you have at least one pair?

   You must select three socks before you have a pair.  The number of
   "pigeonholes", or colors, is two.  When the number of socks exceeds
   the number of possible colors, at least two must be the same color.

   "Pigeonholes" were types of mail slots.
   If there are x pieces of mail and y mail slots, x>y, then at least
   one mail slot will have two pieces of mail.

   If there are more pigeons than pigeonholes, then some pigeonhole must contain
   two or more pigeons.  More generally, if there are more than k times
   as many pigeons as pigeonholes, then some pigeonhole must contain
   at least k+1 pigeons.

   If A and B are nonempty finite sets and |A|>|B|, then there is no
   one-to-one function from A to B.

   Example:  Two people in NYC must have the same number of hairs on their
   heads.  NYC has over 7.5 million people, the average scalp contains
   100,000 hairs.  In fact, we should be able to fill a subway car with
   75 New Yorkesr all of whom have the same number of hairs on their head.

   Example:  There are 20 small towns in a region of west Texas.  We want
   3 people from one of these towns to help us with a survey of their town.
   We advertise in a newspaper that reaches all 20 towns.  How many responses
   to our ad do we need?

   We need at least 41 response (two from each town and one more)

* Languages and Strings

   To study the theory of computation we need to consider models of machines,
   models of the data they manipulate and models of the functions they perform.
   We will represent the data computers manipulate as strings of symbols.

   - symbols
     Any representation component
     1, a, z, 110, $, ...

   - alphabet
     A nonempty finite set of symbols
     English alphabet, for example
     Sigma = {0,1} is an alphabet that we will use often,
	this is the "binary alphabet"

   - string
     A combination of symbols, order is important (abc <> cba)
     One special string is the empty string (no symbols), represented by
	epsilon, labmda, e
     We will often use the variables u, v, w, x, y, z to represent entire
	strings.

     The "length" of a string is the length of the sequence.

   - language
     A subset of the power set of an alphabet (a set of strings)
     A set of strings over a specific alphabet (a language over an alphabet)
     Sigma* is the language over the alphabet Sigma
     Sigma* = {e, 0, 1, 00, 01, 10, 11, 000, 111, ...}

   Two strings over the same alphabet can be combined to form a third string
   using "concatenation".  This is written x.y or xy.  This is the string x
   followed by the string y.  w = x.y iff |w| = |x| + |y|, w(j) = x(j) for
   j=1, ..., |x|, and w(|x| + j) = y(j) for j=1, ..., |y|.

   Concatenation is associative
      (wx)y = w(xy) for any strings w, x, and y.

   A string v is a "substring" of a string w iff there are strings x and y
   (x or y could be empty) s.t. w = xvy.
   Every string is a substring of itself.

   If w = xv, then v is a suffix of w.
   If w = vy, then v is a prefix of w.

   Common English prefixes are "in", "anti", "super"
      infamous, insupportive, insufficient
      supersaturate, supercharge, superhuman

   Common English suffixes are "ly", "tion"
     sufficiently, commotion

   Inductive definition of concatenation (recursive definition)
      w^0 = e
      w^{i+1} = w^i . w, i>=0

      w^1 = w
      (do)^2 = dodo

   We can also concatenate languages.
   If L1 and L2 are languages over alphabet sigma, L = L1.L2 = L1L2, where
      L = {w: w = x.y for some x in L1 and y in L2}.
   L* = L^n, n>=0 (n in N)
      This is called the Kleene closure or Kleene star of a single language.
   L+ = L^n, n>=1 (n in N+)

   Let X be language {a, b, c} and Y be language {abb, ba}.
   Then XY = {aabb, babb, cabb, aba, bba, cba}
   X^0 = {e}
   X^1 = X = {a,b,c}
   X^2 = XX = {aa, ab, ac, ba, bb, bc, ca, cb, cc}

   Inductive definition of reverse
      w^R is the reverse of a string
      1.  If |w| = 0, then w^R = w = e
      2.  If |w| = n+1 > 0, then w = ua for a in Sigma, and w^R = au^R

   - Show inductive proof on strings.
     Prove that for strings w and x, (wx)^R = x^Rw^R.
     (superhuman)^R = (human)^R(super)^R
     We will prove by induction on the length of string x.

     1) Base case.  Let |x| = 0.  Then x = e and (wx)^R = w^R = x^Rw^R.

     2) Inductive Hypothesis.  Assume true for all strings x of length <= n.

     3) Inductive Step.  Show that property then holds for x length=n+1.

	We know x = va, where |v| = n and a in Sigma (a is a single character).
	Then

	   (wx)^R = (w(va))^R = ((wv)a)^R (associativity of concatenation)
			      = a(wv)^R   (definition of reverse)
			      = a(v^Rw^R) (inductive hypothesis)
			      = (av^R)w^R (associativity of concatenation)
			      = (va)^Rw^R (definition of reverse)
			      = x^Rw^R
	Thus the property holds.
        Q.E.D.