Here's a question from a past contest conducted by CMI (Chennai Mathematical Institute).
First of all, the conditions of the question can be broken down into (my interpretation, check if incorrect):
if $i>j$, then, $f(i,j)=f(i-1,j)$
if $i\leq j$ and $i=0$, then, $f(i,j)=0$
And the final condition begining with otherwise can be restated as:
- if $i\leq j$ and $i\neq 0$, then, $f(i,j)=f(i-1,j)+i$
DOUBTS:
I am not sure but the question is apparently self-contradictory. It requires to prove $f(i,j)=\tfrac{i(i+1)}{2}$ but doesn't that lead to a contradiction to the first point? Fix $j$. Increase $i$. So, from $i=0$ to $i=j$, if $f(i,j)=\tfrac{i(i+1)}{2}$ holds, then, $\forall i\geq j$, we have $f(i,j)=f(i-1,j)=\tfrac{j(j+1)}{2}$ and this can be easily understood, else, can be proven by induction. Am I missing something or is the question correct? (My first doubt)
And secondly, the question says : "if multiple conditions apply, consider the first criteria listed. Can there be any multiple criteria case? Either $i\leq j$ or $i > j$. There's no other way, right? (My second doubt)
Kindly clarify the doubts.
You are correct, the problem is poorly worded, and the proposed answer is wrong.
...just iterate for $\,i \le j\,$:
$$\require{cancel} \begin{align} f(0,j) & = 0 \\ f(1, j) &= f(0,j) + 1 = 1 \\ f(2, j) &= f(1,j) + 2 = 1 + 2 \\ \ldots \\ f(i, j) &= f(i-1,j) + i = 1+2+\ldots i = \frac{i(i+1)}{2} \\ \end{align} $$
So in the end:
$$ f(i, j) = \begin{cases} \frac{i(i+1)}{2} \quad\quad i \le j \\ \frac{j(j+1)}{2} \quad\quad i \gt j\end{cases} $$
That can be written as $\,f(i,j)=\frac{\min(i,j)\big(\min(i,j)+1\big)}{2}\,$, but it's still nowhere close to the given answer.
I guess what the problem meant to say was that in the case $\,i \le j\,$ rule #2 applies first, then rule #3 (only) if $\,i \ne 0\,$. That's very poorly worded IMHO.