Refer to answer 1.1 of this file: http://www.dei.unipd.it/~geppo/AA/DOCS/NPC.pdfFrom my understanding and this thread, https://math.stackexchange.com/a/928412, we need 3 steps for that proof.The first case is trivial and true. Now we have assumed the same for i and going to prove that it is true for i+1. I'm unable to clearly see how they have made that deduction in this answer.
How does the induction proof work in this example?
algorithms;correctness proof;induction