Induction is a method that can be used to prove that a mathematical statement holds for possitive integers, n. It usually consists of four steps, as follows: 1) Basis: Show that the statement to be proved holds for n=1 2) Assumption: Assume that the general statement holds for n=k 3) Inductive: Show that the statement holds for n=k+1 4) Conclusion: Conclude that the statement holds for all possitive integers n Example Given that u1 = 6 and un+1 = un + 2n + 4 show that un = 2n + 4n It is important to understand that induction must be applied to the statement to be shown (the one we dont know if it holds for all n). In this case this is un = 2n + 4n Basis n=1: u1 = 2+4 = 6 (from general statement). Statement holds for n=1 (equal to given value) n=2: u2 = 4+8 = 12 (from general statement). u2 = u1 + 2 + 4 = 6 + 2 + 4 = 12 (from requerrence formula) Statement holds for n=2 Assumption Assume that the statement holds for n=k uk = 2k + 4k Inductive n=k+1 Need to show that: uk+1 = 2k+1 + 4(k+1) Use requerrence formula: uk+1 = uk + 2k + 4 = 2k + 4k + 2k + 4 (using assumption above) uk+1 = 2k+1 + 4(k+1) which is equal to the expression that we had to show Therefore, the statement holds for n=k+1 if it holds for n=k Conclusion
The statement holds for n=k+1 if it holds for n=k. Since the stament holds for n=1 and n=2 it now holds for all n, n>=1 by mathematical induction.
2286 Views
See similar Further Mathematics GCSE tutors