Proof by induction — connected skills — 9231 FP1

Notes and key methods

For a recurrence, an induction proof verifies the initial term and then substitutes the proposed expression into the recurrence to obtain the next one. The recurrence, rather than a finite list of terms, supplies the successor relation.

For \(u_{n+1}=ru_n+c\), with \(\displaystyle r\ne 1\), a fixed point is \(\displaystyle L= \frac{c}{1- r}\). The shifted sequence satisfies \(\displaystyle u_{n}-L=r^{n−1}(u_{1}-L)\), which suggests a closed form to prove.

To prove a statement P(n) for all integers \(\displaystyle n\ge n_{0}\), verify \(\displaystyle P(n_{0})\), assume P(k) for an arbitrary \(\displaystyle k\ge n_{0}\), and derive P(k+1) from that assumption. Then state the conclusion for the whole specified domain.

For a sum, the successor is the old partial sum plus the next term. The inductive assumption is a permitted replacement for the old sum; it is not an assumption that the next case is already true.

To prove d divides an expression F(n), aim to write F(n)=dM for an integer M. In an induction step, express F(k+1) in terms of F(k) plus a remainder that is visibly divisible by d.

For example, \(a^{k+1}-b^{k+1}=a(a^k-b^k)+(a-b)b^k\). With integer a,b this shows the factor a−b persists from one exponent to the next.

Check the conditions

• The recurrence and starting index must both be specified.
• The fixed-point expression assumes \(\displaystyle r\ne 1\).
• The integer domain and starting value are stated.
• The successor proof must work for an arbitrary eligible k.
• The divisor is a nonzero integer.
• The quotient introduced in a divisibility proof is an integer.