Proof of Levenshtein distance In the article Levenshtein distance Wikipedia says about the proof of invariant that:


  This proof fails to validate that the number placed in d[i,j] is in
  fact minimal; this is more difficult to show, and involves an argument
  by contradiction in which we assume d[i,j] is smaller than the minimum
  of the three, and use this to show one of the three is not minimal.


So how can I show that d[i,j] is actually minimal? (informal proof is ok)
There is an optimal edit sequence in which the edit operations occur in order from left to right.  There are only three options for the last edit operation: insert the last character of the target string, delete the last character of the source string, or replace the last character.  Everything before the last edit operation must be optimal.

See section 3.7 of this textbook.