Proof by Induction

Proofs Proof by induction is a way to prove that a general statement holds for all (can be used for all but this is less common)

• First prove the general statement for any (generally
• Next assume that the statement is true for
• Show that if the statement is true for it follows that it’s true for
• Conclude that the statement is true for all n (or for all n if you show that it is also true for ) This last step works as after the base case you show that the next number holds, then this becomes a base case and you can keep going to prove for all n