# Strange recursion proof, bivariate induction argument.

Say I have a recursive function defined in the following way

$$f\left(i,j\right) = g\left( f\left(i,\left\lfloor\frac{i+j}{2} \right\rfloor\right),f\left(\left\lfloor\frac{i+j}{2} \right\rfloor,j \right) \right)$$

Consider the conditions $0 \leq i < j \leq n - 1$ and $n \geq 3$. Assuming I start with $i = 0$ and $j = n - 1$ how can I prove that $f$ can be expressed as function of $f(h,k)$ where $k-h+1= 2$? My attempt is an induction argument on $n$, which I'm not sure is correct. If $n = 3$ then

$$f(0,3) = g(f(0,1),f(1,3)) = g(f(0,1),g(f(1,2),f(2,3))),$$

assuming the statement holds until $n$ (strong induction) let's see what happens for $n + 1$ in such a case we have

$$f(0,n) = g\left(f\left(0,\left\lfloor \frac{n}{2} \right\rfloor\right),f\left(\left\lfloor \frac{n}{2} \right\rfloor,n\right) \right)$$

therefore it seems to work, however I believe that this proof is not general enough. Because probably I should work on $(i,j)$ to build the induction cases, but I don't actually know how to do that...

Any clues?

Update: Another attempt based on the difference $j - i$. Let's assume $j - i = 3$ we have $$f(i,j) = f(i,i+2) = g(f(i,i+1),f(i+1,i+2))$$

Let's assume that if $j - i \leq n$ things work, if $j - i = n + 1$ we have $$f(i,j) = g\left(f\left(i,\left\lfloor \frac{i+j}{2}\right\rfloor\right),f\left(\left\lfloor \frac{i+j}{2}\right\rfloor,j\right) \right)$$

however as consequence of the hypothesis we have $$i < \left\lfloor \frac{i+j}{2} \right\rfloor < j$$

Therefore we have $$\begin{array}{l} \left\lfloor \frac{i+j}{2} \right\rfloor - i \leq n \\ j - \left\lfloor \frac{i+j}{2} \right\rfloor \leq n \end{array}$$

Therefore the argument should be proven.

Is this correct?

You need to prove a stronger statement, because as it stands, even with strong induction your inductive hypothesis is not strong enough to say anything about $f\left(\left\lfloor\frac{n}{2}\right\rfloor, n\right)$. What you should be trying to prove by induction is that for any $i$ and $j$ with $0 \leq i < j \leq n$, $f(i, j)$ can be expressed as a function of several $f(h, k)$ (where the various $h$ and $k$ may be different) with $h-k = 1$.
Your second proof seems to hold up. That's clever to induct on the difference $i-j$. Note that the statement above still holds.