How to prove by mathematical induction
A proof by mathematical induction that P(n) is true for every positive
integer n consists of two steps:
1. Basis step. The proposition P(1) is shown to be true.
2. Inductive step. The implication P(n)?P(n+1) is shown to be true for
every positive integer n.
In the inductive step, we usually assume that P(n) is true (this
assumption is called the inductive hypothesis) and try to show that then
Generalization: To show that P(n) is true for every integer n with n?k
(where k can be any integer, including 0 or negative integers), it suffices
1. Basis step: P(k) is true;
2. Inductive step: For every integer n with n?k, if P(n) is true, then so