| Line 3: | Line 3: | ||
Idea: Prove <math>P_0</math> explicitly. | Idea: Prove <math>P_0</math> explicitly. | ||
Design a crank/elevator that proves the following | Design a crank/elevator that proves the following | ||
| − | + | Since <math>P_0</math> has been proven to be true, it shows that there is at least one<math>P_i</math> which is true. | |
| − | + | We have to show that <math>P_{i+1}</math> is also true. | |
Then, induction guarantees that every <math>P_i</math> is true. | Then, induction guarantees that every <math>P_i</math> is true. | ||
Revision as of 20:01, 6 September 2008
The Principle of Induction:
Goal: Collection of statements $ P_0,P_1...P_i $ that we want to prove. Idea: Prove $ P_0 $ explicitly. Design a crank/elevator that proves the following Since $ P_0 $ has been proven to be true, it shows that there is at least one$ P_i $ which is true. We have to show that $ P_{i+1} $ is also true. Then, induction guarantees that every $ P_i $ is true.
