Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| courses:cs211:proof_by_induction [2013/01/03 18:31] – created admin | courses:cs211:proof_by_induction [2013/01/03 18:52] (current) – [Resources] admin | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Proof by Induction ====== | ====== Proof by Induction ====== | ||
| + | |||
| + | ===== Process ===== | ||
| - State your P(n). | - State your P(n). | ||
| Line 8: | Line 10: | ||
| - Prove it! | - Prove it! | ||
| - State your induction hypothesis | - State your induction hypothesis | ||
| - | - State your induction hypothesis! Without it, the whole proof falls apart. Usually it is just restating your P(n) (with no restriction on n) | + | - State your induction hypothesis! Without it, the whole proof falls apart. Usually it is just restating your P(n) with no restriction on n |
| - Inductive Step. | - Inductive Step. | ||
| - Now consider P (n + 1). This is where you try to prove a larger case of the problem than you assumed in your induction hypothesis. What are you trying to prove? Keep this in mind when you do this step. Remember, use your induction hypothesis somewhere, and clearly state where. If you haven’t used your induction hypothesis in this step, then you are not doing a proof by induction. So you’d better need to use it. | - Now consider P (n + 1). This is where you try to prove a larger case of the problem than you assumed in your induction hypothesis. What are you trying to prove? Keep this in mind when you do this step. Remember, use your induction hypothesis somewhere, and clearly state where. If you haven’t used your induction hypothesis in this step, then you are not doing a proof by induction. So you’d better need to use it. | ||
| - | - Conclusion. This is optional. You can re-state | + | - Conclusion |
| + | - Optionally, you can restate | ||
| + | |||
| + | ===== Resources ===== | ||
| + | * [[http:// | ||
| + | * [[http:// | ||
