Math basics › Proofs
Proof by induction
Two parts
Base case: show it is true for the first n, usually 1. Inductive step: assume it for n = k, then prove it for n = k + 1.
Use the assumption
The step only works if you use the n = k case somewhere. Look for it sitting inside the k + 1 version.
For sums
Write the k + 1 sum as the k sum plus one more term, then replace the k sum using your assumption.