(from: https://math.mit.edu/classes/18.417/Slides/alignment.pdf)
The slide on the 11th page talks about how the Edit Distance and the Alignment Distance are equivalent.
I understand how to prove that the Edit Distance will always be less than or equal to the corresponding Alignment Distance. We can always construct a sequence of edits from a given alignments that gives the same result. Since the Edit Distance sequence is the shortest possible, the corresponding sequence is at least as long.
I don't understand how to prove the reverse inequality. Can anyone provide the proof? Apparently one needs to use the triangle inequality to prove it.
On a similar note, are there any resources that treat this topic rigorously? For example, I want proofs of why these two distances satisfy the axioms of metric spaces.