Mathematical Induction and Well-Ordering

Mathematical Induction is a method of proof used to establish the truth of an infinite set of statements indexed by natural numbers. Formal grounding lies in the structure of the natural numbers $\mathbb{N}$ and the Well-Ordering Principle.

The Principle of Mathematical Induction

To prove that $P(n)$ is true for all $n \in \mathbb{N}$ :

Base Case: Demonstrate $P(n_0)$ is true.
Inductive Step: Prove $P(k) \implies P(k+1)$ for all $k \ge n_0$ .

Interactive Lab

def sum_iterative(n):
  return sum(range(1, n + 1))

def sum_inductive_formula(n):
  return (n * (n + 1)) // 2

n_test = 100
print(f"Iterative Sum(100): {sum_iterative(n_test)}")
print(f"Inductive Formula Value: {sum_inductive_formula(n_test)}")
print(f"Match: {sum_iterative(n_test) == sum_inductive_formula(n_test)}")

python

1def sum_iterative(n):

2 return sum(range(1, n + 1))

4def sum_inductive_formula(n):

5 return (n * (n + 1)) // 2

7n_test = 100

8print(f"Iterative Sum(100): {sum_iterative(n_test)}")

9print(f"Inductive Formula Value: {sum_inductive_formula(n_test)}")

10print(f"Match: {sum_iterative(n_test) == sum_inductive_formula(n_test)}")

Strong Induction

In Strong Induction, we assume $P(m)$ is true for all $n_0 \le m \le k$ to prove $P(k+1)$ . This is essential for structures like the Fibonacci sequence.

Interactive Lab

# The Inductive Base: stored in a persistent structure
cache = {0: 0, 1: 1}

def fibonacci(n):
  # Strong induction: we use multiple previous values (n-1 and n-2)
  if n not in cache:
      cache[n] = fibonacci(n - 1) + fibonacci(n - 2)
  return cache[n]

print(f"F(10) = {fibonacci(10)}")
print(f"Current Inductive Cache: {[(k, cache[k]) for k in sorted(cache.keys())[:7]]}...")

python

1# The Inductive Base: stored in a persistent structure

2cache = {0: 0, 1: 1}

4def fibonacci(n):

5 # Strong induction: we use multiple previous values (n-1 and n-2)

6 if n not in cache:

7 cache[n] = fibonacci(n - 1) + fibonacci(n - 2)

8 return cache[n]

10print(f"F(10) = {fibonacci(10)}")

11print(f"Current Inductive Cache: {[(k, cache[k]) for k in sorted(cache.keys())[:7]]}...")

The Well-Ordering Principle

The Well-Ordering Principle states that every non-empty subset of the natural numbers has a least element. This is logically equivalent to the principle of induction.

In the process of Mathematical Induction, what is the 'Inductive Hypothesis'?

Structural Induction

Induction extends to recursively defined structures like Trees.

Base Case: Property holds for leaves.
Recursive Step: If holds for children, it holds for parent.

Interactive Lab

class Node:
  def __init__(self, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

def count_nodes(node):
  if not node: return 0
  # Structural induction: parent = 1 + left + right
  return 1 + count_nodes(node.left) + count_nodes(node.right)

tree = Node(1, Node(2), Node(3, Node(4)))
print(f"Total nodes in tree: {count_nodes(tree)}")

python

1class Node:

2 def __init__(self, val, left=None, right=None):

3 self.val = val

4 self.left = left

5 self.right = right

7def count_nodes(node):

8 if not node: return 0

9 # Structural induction: parent = 1 + left + right

10 return 1 + count_nodes(node.left) + count_nodes(node.right)

12tree = Node(1, Node(2), Node(3, Node(4)))

13print(f"Total nodes in tree: {count_nodes(tree)}")

Mathematical Induction and Well-Ordering

Mathematical Induction and Well-Ordering

The Principle of Mathematical Induction

Strong Induction

The Well-Ordering Principle

In the process of Mathematical Induction, what is the 'Inductive Hypothesis'?

Structural Induction

Can induction be used to prove properties for real numbers (uncountably infinite sets)?