How to prove that a dynamic programming algorithm is a monotonic function I've written an algorithm, which is based on the Needleman-Wunsch algorithm for matching sequences of proteins. This algorithm is a dynamic programming approach, where the optimal matching of two sequences A and B, with length m and n is being calculated by first solving the same problem for the respective substrings.
Currently I'm working on a proof of optimality and one lemma I (think I) need to prove first, is that my algorithm (lets call it A) always yields a score which is higher or equal to the score, than when applying the algorithm to substrings of A and B.
These are my main problems:


*

*The algorithm/function has two dimensions (the "size" of the two substrings)

*Every cell value of the value matrix used in the algorithm is defined to be the maximum of some values, based on values calculated before (overlapping subproblems)


I've found some help regarding multidimensional induction in a blogpost, but I don't know how to approach the max-function.
It would be great if you could give me a hint or a topic I should read about!
Thanks in advance,
das_weezul
EDIT:
Here is a simplified version of the algorithm (Lets call it MATCH). $a_m$ is the m-th symbol of string A, and $b_n$ is the n-th symbol of string B. $SIM(a_m,b_n)$ is the similarity of $a_m$ and $b_n$, which is 1 if $a_m$ and $b_n$ are equal and -1 if not:
$
SIM(a_m,b_n) = \begin{cases}
1, a_m = b_n\\
-1, otherwise
\end{cases}\\
MATCH(0,0) = 0\\
MATCH(0,n) = 0\\
MATCH(m,0) = 0\\
MATCH(m,n) = max \begin{cases}
MATCH(m-1,n-1)+ sim(a_m,b_n)\\
MATCH(m,n-1)\\
MATCH(m-1,n)
\end{cases}
$
What I want to show is something like this:
$MATCH(m-i,n-j) \leq MATCH(m,n), 0 \leq i \lt m \wedge 0 \leq j \lt n $
 A: Isn't that obvious?
$$
MATCH(m,n) = max \begin{cases}
(a): MATCH(m-1,n-1)+ sim(a_m,b_n)\\
(b): MATCH(m,n-1)\\
(c): MATCH(m-1,n).
\end{cases}
$$
Apply (b) recursively, we get
\begin{align}
MATCH(m,n) &\ge MATCH(m,n-1)\\
&\ge MATCH(m,n-2)\\
&\ge \ldots\\
&\ge MATCH(m,n-j).
\end{align}
Now apply (c) recursively and get
\begin{align}
MATCH(m,n-j) &\ge MATCH(m-1,n-j)\\
&\ge MATCH(m-2,n-j)\\
&\ge \ldots\\
&\ge MATCH(m-i,n-j).
\end{align}
Put this two sequences of inequalities together, we obtain
$$MATCH(m,n)\ge MATCH(m-i,n-j).$$
In other words, you first traverse from the node $(m,n)$ horizontally to the left until you reach $(m,n-j)$, then traverse vertically down to the node $(m-i,n-j)$. By the defintion of the $MATCH$ function, the value of the node will decreases along this path.
A: user1151 showed a lot of patience and pushed me into the right direction, so this answer is just for the sake of completeness. Here is the proof I'm using now, feel free to add comments on how to improve it!
Lemma (Monotonicity)
$
MATCH(m,n) \geq MATCH(m-1,n-1), 0 \lt i \leq m \wedge 0 \lt j \leq n
$
Proof
Case 2 max
Per definition: $MATCH(m,n) = MATCH(m-1,n)$
Case 3 max
Per definition: $MATCH(m,n) = MATCH(m,n-1)$
Case 1 ($a_m \equiv b_n \Rightarrow SIM(a_m,b_n) = 1$) max
$MATCH(m,n) = MATCH(m-1,n-1) + 1 \Rightarrow MATCH(m,n) \gt MATCH(m-1,n-1)$
Case 1 ($a_m \neq b_n \Rightarrow SIM(a_m,b_n) = -1$) max
$
MATCH(m,n) = MATCH(m-1,n-1) - 1 \\
$
$
\Rightarrow MATCH(m-1,n-1) -1 \geq MATCH(m-1,n) \\ 
\wedge MATCH(m-1,n-1) -1 \geq MATCH(m,n-1)
$
$
\Rightarrow MATCH(m-1,n-1)  \gt MATCH(m-1,n) \\ 
\wedge MATCH(m-1,n-1)  \gt MATCH(m,n-1) \\
$
$
MATCH(m-1,n) \lt MATCH(m-1,n-1) \\
\Rightarrow\Leftarrow MATCH(m-1,n) = MATCH(m-1,n-1)
$ (Contradiction to Case 2 max)
$
MATCH(m,n-1) \lt MATCH(m-1,n-1) \\
\Rightarrow\Leftarrow MATCH(m,n-1) = MATCH(m-1,n-1)\\
$ (Contradiction to Case 3 max)
Q.E.D
The last part of the proof shows that the algorithm will never match two different symbols.
