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?


1 Answer 1


The following is based on the question before the edit:

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$.

After the edit:

Your second proof seems to hold up. That's clever to induct on the difference $i-j$. Note that the statement above still holds.

  • $\begingroup$ So the second one is fine I assume, probably not rigorous enough but it should be formal and correct I suppose. Is it? $\endgroup$ Jul 11, 2017 at 8:58
  • $\begingroup$ Basically everything that you need in the second argument is there. Just make sure you correctly state what you are proving by induction. $\endgroup$ Jul 11, 2017 at 12:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .