Proof by induction

• In general, the first step is basis: write out the statement and prove it is true for a starting value, usually n = 1.
• In general, the second step is assumption: assume the statement is true for n = k, where k is a positive integer.
• In general, the third step is inductive: use the assumption to prove the statement is true for n = k + 1.
• In general, the fourth and final step is conclusion: the statement is true for n = 1, and assuming n = k, then the statement is true for all n + 1, and is therefore true for all values of n.
• For series, in the inductive step, use the fact that $\sum ^{k+1} _ {r=1}$ f(r) = $\sum ^k _ {r=1}$ f(r) + f(k + 1).
• For divisibility statements, in the inductive step, consider f(k + 1) - a f(x), where a is a constant in order to cancel out terms.
• For matrices, in the inductive effect, use the fact that $\begin{pmatrix} a & b \\ c & d\end{pmatrix}^{k+1}$ = $\begin{pmatrix} a & b \\ c & d\end{pmatrix}^k$ $\begin{pmatrix} a & b \\ c & d\end{pmatrix}$ .