# Using induction vs invariants to prove correctness of algorithms

In my algorithms class I have generally been proving algorithms by induction. So for example, given some algorithm $$A(n)$$ that computes $$x$$, I show that the algorithm works for some base case, say $$A(1)$$, then I assume that the algorithm will work for $$k. Then I show that the algorithm works for some $$z=n$$. Are there cases where this won't work or where this isn't recommended? I see algorithms textbooks commonly define loop invariants, and then show that the invariant holds before and after the loop. Is this approach always necessary when dealing with loops? Can't I just assume that it will work for the case where $$z=n-1$$ and then show it works for $$z=n$$ i.e. using normal/strong induction?

• If your loops are all simple... – gnasher729 Sep 28 '19 at 21:52
• I guess we've just been working through recurrences and easy loops, since direct induction seemed the most intuitive for me to prove correctness. – lmeninato Sep 28 '19 at 22:05