Question

When you should use Induction as a way to prove an algorithm's
correctness?

Answer 1

Simple Induction

Proof: By induction on n we prove the following statement for all n:

P(n): blabla n blabla.

Step (n→n+1): Assume the statement P(n) holds for n (I.H.). Show that P(n+1) holds (assuming that P(n) holds. ...

By induction we can conclude that the statement holds for all n.