We have seen that binomial coefficients, Fibonacci and Lucas numbers, and factorials may be defined inductively, that is, by giving their initial values and describing how to get new values from previous values. Similarly, one may define an arithmetic progression a₁, a₂, ... , a_t as one for which there is a fixed number d such that a_n+1 = a_n + d for n = 1, 2, ..., t - 1. Then the values of a₁ and d would determine the values of all the terms. A geometric progression b₁, ... , b_t is one for which there is a fixed number r such that b_n+1 = b_nr for n = 1, 2, ... , t - 1; its terms are determined by b₁ and r.

It is not surprising that mathematical induction is very useful in proving results concerning quantities that are defined inductively, however, it is sometimes necessary or convenient to use an alternate principle, called strong mathematical induction.
 

STRONG MATHEMATICAL INDUCTION: A statement concerning positive integers is true for all the positive integers if there is an integer q such that (a) the statement is true for 1, 2, ... , q, and (b) when  the statement being true for 1, 2, ... , k implies that it is true for k + 1.

As in the case of the previous principle, this can be modified to apply to statements in which the starting value is an integer different from 1.
 

Saturday, April 11, 1998