Suppose you want to prove that you can climb all the way to the top of a ladder. One way to do this is in two parts: First prove you can stand on the bottom step. Call this step 1 and number the rest of the steps 2,3,..N upward to the top of the ladder.
The second part is to prove that if you are on any step K, you know how to take one step upward to step K+1. (I'm not telling you how to do that here. But suppose you know how.) This is called the "inductive step." (Pun intended.) The principle of indication is that these two proof parts taken together provide the desired proof. In this case, the proof is constructive. (This isn't always true.) You effectively get an algorithm for climbing the ladder as a byproduct of proof: Stand on the first step 1. Now use the inductive step with K=1 to get to step K+1 = 2. Use it again with K=2 to get to K+1=3. Continue using N-1 times. This puts you at the top of the ladder. Note that in computer science you often need more complex kinds of induction - for example over data structures - rather than integers. For a simple example, take induction over trees. Prove that complete binary trees (where all nodes are either leaves or have 2 children) always have an odd total number of nodes. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/VylCYcZsknAJ. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
