```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.
```