Consequences of induction - another link in the chain

Let's use our familiar strong induction to prove another property of the integers, namely that for any positive $k$, $k$ is the same as $k$ copies of 1 all added together. We'll actually prove this for any non-negative $k$, or (equivalently), for any $k \in \mathbb{N}$.

(Generating Positive Integers) Every non-negative integer $k$ is equal to the sum of 0 and some number of ones - i.e. $0 + 1 + 1 + \cdots + 1$.
I'm going to give you not one, but two proofs of this fact! One by weak induction and one by strong induction. It may help you see the difference. We will mostly use strong induction going forward because it is generally easier to use, though in this case weak induction works perfectly!
weak induction   strong induction
We proceed by (weak) induction on $k$. Our predicate $P(x)$ is that $x$ can be written as $0 + 1 + 1 + \cdots + 1$. If $k=0$ then $k$ is 0 plus zero 1s, so $P(0)$ is true. The inductive case is: 
1: P(k)                        [Assumption A]
2: k     = 0 + 1 + ... + 1     [definition of P(k)]  
3: k + 1 = k + 1               [reflex. of equality]
4: k + 1 = 0 + 1 + ... + 1 + 1 [subst. of 3 using 2]
5: P(k+1)                      [definition of P]
5: P(k) => P(k+1)              [close assumption]
By the principle of induction $P(k)$ holds for all non-negative $k$. 		  We proceed by (strong) induction on $k$. If $k=0$ then $k$ is 0 plus zero 1s. If $k>0$, then $k-1$ greater than or equal to zero by the Gap Theorem, and $k-1 \lt k$, so by the inductive hypothesis, $k-1$ is equal to $0$ plus $k-1$ 1s. So we get $$ k-1 + 1 = \underbrace{0+1+\cdots+1}_{=k-1\text{ by inductive hyp.}}+1 = k $$ and deduce that every non-negative integer $k$ can be written this way.

So we have proved that all positive integers are generated from zero by adding 1s. Crucially, that means that there are no positive elements that satisfy our axioms (non-trivial commutative ordered ring with the axiom of induction) but cannot be generated this way. And, of course, all negative integers are generated from zero by adding -1s (can you prove that?). Notice that the Generating Positive Integers theorem also tells us that if you keep subtracting 1 (adding -1) from a positive number you eventually arrive at zero!

Important! Another big deal about is that it justifies us using our usual numbers (like 3, or -5, or 42) as constants. The constant $k$ stands for $0$ with $k$ copies of "+ 1" tacked on the end. So, for example:
constant 3 is $0 \underbrace{+ 1 + 1 + 1}_{\text{three +1s}}$, constant -2 is $-(0 \underbrace{+ 1 + 1}_{\text{two +1s}})$, no-negative constant $k$ is $0 \underbrace{+ 1 + \cdots + 1}_{\text{$k$ +1s}}$
Not only can I use our usual numbers as constants, but I can use our usual arithmetic on those constants. For example, when I say 2 + 3 = 5, I am saying that two 1s added together + three 1s added together is the same as five 1s added together. More fundamentally, I can say $1 + 1 = 2$ because I know it means that one +1 added to one more +1 gives me two +1s.

Definitions of even and odd

One of the most fundamental properties of integers is their parity, i.e. their evenness/oddness. So we need to define this notion formally. It is convenient to introduce the predicates $\text{even}(\cdot)$ and $\text{odd}(\cdot)$ that are true when their argument is even or odd as appropriate and false otherwise.
$n$ is even if and only if $\exists k[n=2*k]$.
Note: In full first order logic this would be written as $\forall n[\text{even}(n) \Leftrightarrow \exists k[n=2*k]]$.
$n$ is odd if and only if $\exists k[n=2*k+1]$.
Note: In full first order logic this would be written as $\forall n[\text{odd}(n) \Leftrightarrow \exists k[n=2*k+1]]$.

ACTIVITY The following are results you should be able to prove without induction. They are all pretty straightforward.

  1. Here is a prose proof that 7 is odd: $7 = 2*3+1$.
    Why is "$7 = 2*3+1$" sufficient? Write a numbered step-by-step first-order logic style proof that starts with $7 = 2*3+1$ as given, and proves $\text{odd(7)}$.
    Note: from now on we will give prose proofs and skip the step-by-step unless explicitly required to do otherwise.
  2. Prove that 28 is even and 73 is odd. Prove that 0 is even and prove that -1 is odd.
  3. Prove that the sum of two even numbers is even.
  4. Prove that the sum of two odd numbers is even.
  5. Prove that if n is an odd positive number, then -n is odd.

Activity problems - some solutions

Normally I don't post solutions to "Activities", but in this case I think it will be productive.
  1. Step-by-step proof that given 7=2*3+1, 7 is odd: 
    1: 7 = 2*3 + 1                      [Given]
2: ∃k[7 = 2*k + 1]                  [Existential introduction on 1]
3: ∀n[odd(n) <=> ∃k[n = 2*k + 1]]   [definition of odd]
4: odd(7) <=> ∃k[7 = 2*k + 1]       [specialize n to 7 in 3]
5: ∃k[7 = 2*k + 1] => odd(7)        [equivalence splitting on 4]
6: odd(7)                           [modus ponens on 5 and 2]

    Note: From now on, to prove a number is odd, we will take it as sufficient to write it as "2 * something + 1", since the remainder of the proof (lines 2-7 above) is boilerplate - i.e. it's the same regardless of what it is we are trying prove the oddness of. Similarly, if we can write a number as "2 * something" we will take that as sufficient for proving that the number is even. So, in the future, our proof that, for example, 11 is odd will look like:

    11 = 2*5 + 1, so 11 is odd.

  2. Prove that 28 is even and 73 is odd. Prove that 0 is even and prove that -1 is odd.
    28 = 2*14 ... so 14 is "k"
    73 = 2*36 + 1 ... so 36 is "k"
    0 = 2*0 ... so 0 is "k"
    -1 = 2*(-1) + 1 ... so -1 is "k"
  3. Prove that the sum of two even numbers is even.
    Assume $n_1$ and $n_2$ are even. Then by the definition of even, $n_1 = 2*k_1$ and $n_2 = 2*k_2$ for some $k_1$ and $k_2$. So $ n_1 + n_2 = 2*k_1 + 2*k_2 = 2*(k_1+k_2) $ so $n_1+n_2$ is even ("$k$" is $k_1+k_2$).

    Note: this "prose proof" is acceptable, because (hopefully!) all of you could "fill in the blanks" and produce a full first-order proof if you had to:

    prose proof lines filling in the blanks
    Assume $n_1$ and $n_2$ are even. 
    1: even(n1)		    
2: even(n2)
    Then by the definition of even, $n_1 = 2*k_1$ and $n_2 = 2*k_2$ for some $k_1$ and $k_2$. 
    3: ∀n[even(n) <=> ∃k[n = 2*k]] [Definition of even]
4: even(n1) <=> ∃k[n1 = 2*k]   [Specialization of 3 using n=n1] 
5: even(n1) => ∃k[n1 = 2*k]    [Equivalence splitting]
6: ∃k[n1 = 2*k]                [Modus ponens 5, 1]
7: n1 = 2*k1                   [Existential instantiation on 6]
8: even(n2) <=> ∃k[n2 = 2*k]   [Specialization of 3 using n=n2] 
9: even(n2) => ∃k[n2 = 2*k]    [Equivalence splitting]
10: ∃k[n2 = 2*k]               [Modus ponens 5, 1]
11: n2 = 2*k2                  [Existential instantiation on 6]
    So $n_1 + n_2 = 2*k_1 + 2*k_2 = 2*(k_1+k_2)$ 
    12: n1 + n2 = n1 + n2          [Reflex. of equal]
13: n1 + n2 = 2*k1 + 2*k2      [Subst. of equal on 12 using 7,11]
14: n1 + n2 = 2*(k1 + k2)      [Ring axiom 3.i (distributivity)]
    so $n_1+n_2$ is even 
    15: ∃k[n1 + n2 = 2*k]   [Existential intro on 14, k = k1 + k2]
16: even(n1 + n2) <=> ∃k[ n1 + n2 = 2*k]  [Spec. 3, n = n1 + n2]
17: ∃k[ n1 + n2 = 2*k] => even(n1 + n2)   [Equiv. split. on 16]
18: even(n1 + n2)                         [Modus ponens 17, 15]

  4. Prove that the sum of two odd numbers is even.
    Assume $n_1$ and $n_2$ are odd. Then by the definition of odd, $n_1 = 2*k_1+1$ and $n_2 = 2*k_2+1$ for some $k_1$ and $k_2$. So $ n_1 + n_2 = 2*k_1 + 1 + 2*k_2 + 1 = 2*(k_1+k_2) + 2 = 2*((k_1+k_2)+1) $ so $n_1+n_2$ is even ("$k$" is $k_1+k_2+1$).
  5. Prove that if $n$ is an odd positive number, then $-n$ is odd.
    Assume $n$ is odd, then $n = 2*k+1$ for some $k$. $-n = -1*n = -1*(2*k+1) = 2*(-k) + -1 = 2*(-k) + (-2 + 2) + -1 = 2*(-k + -1) + 1$. So $-n$ is odd ("k" is $-k + -1$).
Christopher W Brown