Let s1 and s2 are 2 arbitrary strings with lengths l1 and l2.

Levenshtein distance $lev(A, B)$ between strings $A$ and $B$ is a minimal number of insert, delete and replace that is required to perform on string A to become string B. Inserting, deleting and replacing is allowed to perform at any point of the strings (not just at the beginning or end).

Let's define a matrix $M$ with size $l1 \times l2$ such that: $$M[i][j] = lev(s1[0..i], s2[0..j])$$ s1[0..i] is a substring of s1 staring index 0 (inclusive) ending index i (exclusive).

s2[0..j] is a substring of s2 staring index 0 (inclusive) ending index j (exclusive).

Prove that $$M[i][j] = \min (M[i-1][j-1] + 1, M[i - 1][j] + 1, M[i][j-1] + 1), s1[i] \ne s2[j]$$$$M[i][j] = M[i-1][j-1], s1[i] = s2[j]$$

This is in fact a proof of correctness of Wagner–Fischer algorithm to compute the Levenshtein distance using dynamic programming, but it's completely not obvious to me why this is correct.

My first thought was to go with induction performing the step, but in case, say $s1[i]=s2[j]$ how is it possible to prove that every alternative path would be at least $M[i−1][j−1]$ long.

The complicated thing about the problem is that a shortest path is definitely not unique.