Mathematical Induction

A statement involving a natural number

A statement involving a natural number n that can be either true or false for each value of n. For example, p(n): 1 + 2 + 3 + ... + n = n(n+1)/2. We w

Verify that the statement p(1)

Verify that the statement p(1) is true by direct calculation. This establishes that our statement works for the smallest natural number. Sometimes we

Assume that the statement p(k)

Assume that the statement p(k) is true for some natural number k. This assumption is crucial - we don't prove p(k) is true, we simply assume it and us

Using the inductive hypothesis p(k)

Using the inductive hypothesis p(k), prove that p(k+1) must also be true. This typically involves algebraic manipulation where we express the (k+1) ca

For statements like 'f(n) is divisible

For statements like 'f(n) is divisible by d', we prove f(k+1) = f(k) + [expression divisible by d], showing f(k+1) is also divisible by d. Common tech