Proof of Levenshtein distance
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.