Here is an example of proof by induction.

Proposition:

Proof: in order to prove this we will follow the instructions shown in the previous page. First let for our base case. . Therefore our base case is true.

Now for our inductive hypothesis. We now assume that is true for and now we prove for the case .

We can collapse that part because of our inductive hypothesis.

This proves that .

Induction proofs are used to prove closed forms and greedy algorithms which are both important components in the design and analysis of algorithms. Generally speaking proof of induction is used for statements of facts more often then for statements such as “if P then Q” or “P if and only if Q”.

- What is a proof?
- Direct Proof Part I
- Direct Proof Part II
- Proof by Contradiction
- Proof by Induction
- Proof by Induction example
- Proof by Contrapositive
- Proof of Existence
- Proof of Uniqueness
- Disproof
- Conclusion

*Filed under : Mathematics*