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 .