Topics in this course:

  Induction *
  Program and Algorithm correctness **
  Propositional and Predicate Logic
    - as a topic of study, not just for use
  Regular Expressions, Finite State Automta, and Languages *

Number of *s gives a rough idea of how hard students seem to
 find these topics. YMMV (your mileage may vary).


Consider the following program:

  a = 1/5
  while (true)
    print a
    a = (1 + a) / 2

To begin to understand it we calculated a few values of a:

  1/5
  3/5
  4/5
  9/10
  19/20

We conjectured:

  a is increasing
  a is always < 1

We justified that a is always < 1 by:

  a starts off < 1

  if a < 1 then replacing it with (1 + a) / 2 gives us a new value
   < (1 + 1) / 2 = 1.
   
This is inductive thinking: the property is true at the start, and
 each step preserves the truth. Thus it is always true.


Recall that in Java and python, variables can have their values vary.
There is a distinction between a variable and its value, but by now you
 understand this well enough that we don't have to point out every time
 which we mean.

Mathematical variables don't vary: they represent a fixed but possibly
 unknown value.

For n in N (natural numbers N = {0, 1, 2, ...}), let a_n be the value
 of the variable a after n iterations. In particular a_0 means the
 initial value of a.

Now we can write up our justification as:

  Base case: a_0 = 1/5 < 1.

  Inductive Step:

    Suppose n in N,
     and a_n < 1 [inductive assumption].

    Then a_(n+1) = (1 + a_n) / 2 [from the code]
                 < (1 + 1) / 2   [from the inductive assumption]
                 = 1

  So, by Induction, a_n < 1 for all n in N.

What precisely is Induction?
It is the following principle (which we assume is true):

  [P(0) /\ \-/n in N,(P(n)->P(n+1))] -> \-/n in N, P(n)

Think about how our justification used this principle.
Recall your work in CSC165 about proof structures.

A common style for writing up an inductive proof of \-/n in N, P(n) is:

  We prove this by induction.

  Base Case ___ P(0).
  ---------

  Inductive Step
  --------------
    Suppose n in N.
    Assume P(n).
    ___ P(n+1)
     (you will use P(n) to help fill in the blank and
       refer to it as "the inductive assumption/hypothesis" or "IH")

  So by Induction, \-/n in N, P(n).

If the nth claim is not clear, you begin with more detail:

  For n in N, let P(n) be "___".

  We prove that \-/n in N, P(n) by induction.

  ...

Recall from CSC165 that P(n) must be open in n, and be boolean.