FP3 Topic 6: Proof by induction
Sequences
How to prove a formula for a sequence when given the iterative definition.
Given that un+1 = 2un+1 and u1=3, prove that un=2n+1 - 1
You can show that this formula is true for any value of n that you choose. But does this prove that the statement is true for every value of n from 1 to infinity? Unfortunately not. Mathematics requires a logical general proof of any statement. This formula can be proved by using proof by induction. The following lines show such a proof step by step. Use your mouse to drag the statements into the correct order. The gauge shows if you are moving in the right direction.

Summary To prove a theorem by the method of induction it is common practice to refer to the statement of the theorem by P(n), meaning "Proposition n". The proof will have three parts: The initial step This is where you show the statement is true for the first value of n, normally n=1. In other words you show that P(1) is true. This step is usually trivially easy. The induction hypothesis Here you assume that the statement is true for a specific value of n, say when n=k. In other words, you assume P(k) is true. The induction step This is the complicated part which requires the most thought, particularly concerning the algebra involved. You have to show that P(k) implies P(k+1) An applet written for the site by Advisory Matters