Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Proof Template

Every proof follows mathematical induction in two steps:

  • basis step: check the statement for the smallest
  • inductive step: assume it holds for and prove it for

Exam tips from the crash course:

  • write LHS and RHS separately, do not work on both sides at the same time
  • the usual step is , but a statement about only odd or even needs
  • remember the standard sums and

Example 1: Sum of Integers

Prove for all .

Basis: for , LHS and RHS .

Inductive step: assume it holds for . Then

which is the formula with .

Example 2: Geometric Sum

Prove for all and .

Basis: for , LHS and RHS .

Inductive step:

Example 3: Inequality with Powers

Prove for integers .

Basis: for , .

Inductive step: assume . Expand the target RHS:

Split the LHS the same way:

Compare term by term:

  • by the assumption
  • since
  • since

Adding the three gives , so the statement holds for .

Example 4: Factorial versus Power

Prove for integers .

Basis: for , .

Inductive step: assume . Then

using for .