Induction with two(?!) variables
================================
Consider Pascal's Triangle, where each element is the sum of the two
 above left and above right (or just the one, if there is only one),
 with 1 at the top:

          1
        1   1
      1   2   1
    1   3   3   1
  1   4   6   4   1
         ...

In lecture I asked you to suggest an indexing scheme, and you said:

                  p(0, 0)
              p(1, 0) p(0, 1)
          p(2, 0) p(1, 1) p(0, 2)
      p(3, 0) p(2, 1) p(1, 2) p(0, 3)
  p(4, 0) p(3, 1) p(2, 2) p(1, 3) p(0, 4)
                ...

So we define p by:

  For i, j in N,
    p(i, 0) = p(0, j) = 1
    p(i+1, j+1) = p(i+1, j) + p(i, j+1)

We need something to prove about p.
How about the following: p(i, j) = (i+j)!/(i!j!) for all i, j in N.

For i, j in N let Q(i, j) be: p(i, j) = (i+j)!/(i!j!).

What is going on inductively? Each level depends on the previous.

So let's make R(n) be: for all (i, j) from level n, Q(i, j).
 We try to prove R(n) for all n, inductively.

What level is (i, j) in? Level i + j.

So more precisely, for n in N let R(n) be:
  For all i, j in N such that i + j = n, Q(i, j).

As usual, I point out that this is open in (and only in) n, and makes
 a claim.

Since for each i, j in N, i + j is some number in N, proving \-/n in N, R(n)
 will prove \-/i,j in N, Q(i, j).

Proof
-----
  Base Case (0th level)
  ---------
  R(0) is: For all i, j in N such that i + j = 0, Q(i, j).

  Let i, j in N. Suppose i + j = 0.

    Then i = j = 0.
    p(0, 0) = 1 by definition of p.
    (i+j)!/(i!j!) = 0!/(0!0!) = 1.

  Inductive Step
  --------------
  Let n in N. Suppose R(n).

    Let i, j in N. Suppose i + j = n + 1.

    Case 1: i = 0
    -------------
    Then p(i, j) = 1.
    (i+j)!/(i!j!) = j!/j! = 1.

    Case 2: j = 0
    -------------
    Then p(i, j) = 1.
    (i+j)!/(i!j!) = i!/i! = 1.

    Case 3: i, j > 0
    ----------------
    Then i-1, j-1 in N, so by the definition of p:
      p(i, j) = p(i, j-1) + p(i-1, j)
    
    Since i + (j - 1) = n + 1 - 1 = n and (i - 1) + j = n + 1 - 1 = n,
     by the IH:
      p(i, j-1) = (i + j-1)!/(i!(j-1!)) = n!/(i!(j-1)!)
      p(i-1, j) = (i-1 + j)!/((i-1)!j!) = n!/((i-1)!j!)

    So
      p(i, j) = n!/(i!(j-1)!) + n!/((i-1)!j!)
              = (n!j + n!i)/(i!j!)
              = n!(i+j)/(i!j!)
              = n!(n+1)/(i!j!)
              = (n+1)!/(i!j!)
              = (i+j+1)!/(i!j!)
    
    By the way, it wasn't necessary to change i+j in the numerator to n, since
     we eventually changed it back, but it looked a bit neater to me.