Hoorcollege 10(Hoofdstuk 9):
We can then define a functions over N by induction. For example, we may want to compute the sum
of the first n numbers: 1 + 2 + 3 + … + n. We can do so using an inductive definition:
sum(0) = 0
sum(n + 1) = (n + 1) + sum(n).
Claim: For all n, we can show that sum(n) = n×(n+1) 2 . How to prove this? Let’s check that the
equality holds for the first few numbers:
if n = 0, we have that sum(0) = 0 = (0×1) / 2 .
if n = 1, we have that sum(1) = 0 + 1 = 1 = (1×2) / 2 .
if n = 2, we have that sum(2) = 0 + 1 + 2 = 3 = (2×3) / 2 . But we need proof.
Proof by induction:
We defined the set of natural numbers using the following two clauses:
0∈N
for any n ∈ N, the number (n + 1) ∈ N.
To show that some property P holds for all natural numbers, it suffices to show:
P(0)
for all n, if we assume that P(n) we need to show that P(n + 1)
Example proof by induction where we will proof the base case and inductive case as well:
Claim: For all n, we can show that sum(n) = n×(n+1) 2 . Proof: We prove this statement by induction
on n.
if n = 0, we need to show that sum(0) = (0×1) / 2 .
Suppose that n = k + 1 and that sum(k) = (k×(k+1)) / 2 .
We need to show sum(k + 1) = (k+1)(k+2) / 2 .
Base Case proof: If n = 0, we need to show that sum(0) = (0×1) / 2 . Using the definition of sum, we
know that sum(0) = 0 = (0×1) / 2 as required. This completes the base case.
Inductive case proof: Suppose that that sum(k) = (k×(k+1)) / 2 . We need to show sum(k + 1) = ((k+1)
(k+2)) / 2 :
We can then define a functions over N by induction. For example, we may want to compute the sum
of the first n numbers: 1 + 2 + 3 + … + n. We can do so using an inductive definition:
sum(0) = 0
sum(n + 1) = (n + 1) + sum(n).
Claim: For all n, we can show that sum(n) = n×(n+1) 2 . How to prove this? Let’s check that the
equality holds for the first few numbers:
if n = 0, we have that sum(0) = 0 = (0×1) / 2 .
if n = 1, we have that sum(1) = 0 + 1 = 1 = (1×2) / 2 .
if n = 2, we have that sum(2) = 0 + 1 + 2 = 3 = (2×3) / 2 . But we need proof.
Proof by induction:
We defined the set of natural numbers using the following two clauses:
0∈N
for any n ∈ N, the number (n + 1) ∈ N.
To show that some property P holds for all natural numbers, it suffices to show:
P(0)
for all n, if we assume that P(n) we need to show that P(n + 1)
Example proof by induction where we will proof the base case and inductive case as well:
Claim: For all n, we can show that sum(n) = n×(n+1) 2 . Proof: We prove this statement by induction
on n.
if n = 0, we need to show that sum(0) = (0×1) / 2 .
Suppose that n = k + 1 and that sum(k) = (k×(k+1)) / 2 .
We need to show sum(k + 1) = (k+1)(k+2) / 2 .
Base Case proof: If n = 0, we need to show that sum(0) = (0×1) / 2 . Using the definition of sum, we
know that sum(0) = 0 = (0×1) / 2 as required. This completes the base case.
Inductive case proof: Suppose that that sum(k) = (k×(k+1)) / 2 . We need to show sum(k + 1) = ((k+1)
(k+2)) / 2 :
