Can you explain induction and go through an example?

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 u₁ = 6 and u_n+1 = u_n + 2ⁿ + 4 show that u_n = 2ⁿ + 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 u_n = 2ⁿ + 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  u_k = 2^k + 4k  Inductive n=k+1 Need to show that: u_k+1 = 2^k+1 + 4(k+1)  Use requerrence formula:  u_k+1​ = u_k + 2^k + 4 = 2^k + 4k +  2^k  + 4 (using assumption above) u_k+1​ = 2^k+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.