I looked into this last year while teaching. The other answers, including Prof. Erickson's excellent book, feel incomplete, because they handwave a step along the lines of "there is an optimal edit sequence that proceeds left-to-right" or "we start by lining up the two words in columns vertically...."
(Even if that feels obvious, can you easily answer: does the proof generalize if we are given a different nonnegative cost for each possible insertion, deletion, and modification? I only found the answer in one of the original edit distance papers, I forget which. It does generalize if the optimal edit cost satisfies the conditions of a distance metric, as you can probably see from the following proof sketch.)
There are definitely other ways to do it, maybe more elegant ones, but this should work.
Lemma. In an optimal sequence of edits from string $X$ to $Y$, the only possible operations are the following forms:
- deletion of a character in $X$
- insertion of a character in $Y$
- modification of a character in $X$ to a different character in $Y$
Proof sketch. Given an edit sequence that contains an edit not of the above form, we can modify it to a strictly shorter (or "lower cost") sequence. For example, suppose we delete a character that was not originally in $X$. Then this character was either originally inserted at some point, or it was modified at some point. In the first case, we can remove the insertion and deletion steps entirely, and obtain an edit sequence that still transforms $X$ into $Y$, but is two steps shorter. In the second case, we can remove the previous modification step, but leave the deletion step. Now the edit sequence still transforms $X$ into $Y$, but is one step shorter. Similarly, one can check that edit sequences containing insertions or modifications not of the above form are strictly suboptimal. $\square$
Claim. Given strings $X$ and $Y$ of length $m$ and $n$, let $d[i,j]$ be the edit distance between the prefix of $X$ of length $i$ and the prefix of $Y$ of length $j$. Then for $1 \leq i \leq m$ and $1 \leq j \leq n$,
$$ d[i,j] = \min\begin{cases} d[i-1,j] + 1 \\ d[i,j-1] + 1 \\ d[i-1,j-1] + \mathbb{1}[X_i \neq Y_j] \end{cases} . $$
Proof sketch. Consider an optimal edit sequence transforming $X[1:i]$ into $Y[1:j]$. Because $X_i$ and $Y_j$ are the final characters in their respective strings, the Lemma implies (with some thought) that at least one of the following must occur:
$X_i$ is deleted
$Y_j$ is inserted
$X_i$ becomes $Y_j$, either by being unchanged (if $X_i==Y_j$) or by being modified.
Now we observe that in any of these cases, we can make that edit the final edit in the sequence, because they are independent of all other edits in the sequence. In Case 1, the previous edits transform $X[1:i-1]$ into $Y[1:j]$, so the total length is $d[i-1,j] + 1$. Cases 2 and 3 are analogous. Since these are the only three possibilities, the optimal edit sequence is the minimum of them. $\square$