page1
Template for Proofs by Mathematical Induction
1. Express the statement that is to be proved in the form “for all n  b, P(n)” for a fixed integer b.
2. Write out the words “Basic Step.” Then show that P(b) is true, taking care that the correct value b is used. This completes the first part of the proof.
3. Write out the words “Inductive step.”
4. State, and clearly identify, the inductive hypotheses, in the form “assume that P(k) is true for an arbitrary fixed integer k  b.”
5. State what needs to be proved under the assumption that the inductive hypothesis is true. That is, write out what P(k+1) says.
6. Prove the statement P(k+1) making use of the assumption P(k). Be sure that your proof is valid for all integers with k  b, taking care that the proof for small values of k, including k=b.
7. Clearly identify the conclusion of the inductive step, such as “this completes the inductive step.”
8. After completing the basic and inductive steps, state the conclusion, namely that by mathematical induction, P(n) is true for all integers n  b.
Sequences and summations:
1) Arithmetic sequence: 2, 5, 8, 11, … 2) Geometric sequence: 2, 6, 18, 54, ...
a0 initial term/value, a0 = 2; a0 is initial term/value, a0 = 2
d is common difference, d = 3 r is common ratio, r = 3
an = a0 + dn is nth term an = a0  rn is nth term
Partial sums:
Other useful summation formulas:
, where C is a constant
A rule that defines a term an as a function of previous terms in the sequence is called a recurrence relation.
In a recursive definition of a function, the value of the function is defined in terms of the output value of the function on smaller input values. Recursion is the process of computing the value of a function using the result of the function on smaller input values.
Components of a recursive definition of a set:
A recursive algorithm is an algorithm that calls itself. It has a base case in which the output is computed directly on an input of small size or value. On a larger input, the algorithm calls itself on an input of smaller size and uses the result to construct a solution to the larger input. An algorithm's calls to itself are known as recursive calls.
A basis explicitly states that one or more specific elements are in the set.
A recursive rule shows how to construct larger elements in the set from elements already known to be in the set. (There is often more than one recursive rule).
An exclusion statement states that an element is in the set only if it is given in the basis or can be constructed by applying the recursive rules repeatedly to elements given in the basis.