# Recurrence with Minimum

I need to solve the following recurrece:

$$T(n,m)=\begin{cases} 1, & m\leq 2(n-1)!\\ \min\limits_{a,b\geq 1\\a\cdot b\leq (n-1)!}{T(n-1,a)+T(n-1,b)+T(n,m-ab)}, & \text{else} \end{cases}$$

Note: in the first line beneath the $$\min$$ we have $$a,b$$ and in the next line it's $$a\cdot b$$.

I find it difficult to solve this recurrence as it contains $$\min$$, so I tried to calculate the minimum, but I didn't know how to prove it (I believe that the minimum occurs at $$a=b=\sqrt{(n-1)!}$$, but I don't know how to prove it...). So I am stuck with this.

Any help would be highly appreciated!

Edit:

Experiments show that

$$T(n,m)=\begin{cases}1 & f(n,m)\leq 0\\ 3+2\Big\lfloor\frac {f(n,m)-1}{(n-1)!}\Big\rfloor & \text{else}\end{cases}$$

for $$f(n,m)=m-2(n-1)!$$, and considering the $$\min$$ of an empty set to be infinity.

• Is $T(n,m)$ defined on $\Bbb Z\times\Bbb Z$ or $\Bbb Z_{\ge0}\times\Bbb Z_{\ge0}$ or $\Bbb Z_{\ge1}\times\Bbb Z_{\ge1}$? If $(n,m)=(2,1)$ or $(n,m)=(2,2)$, then $f(n,m)\le0$ and $n\le2$. According to your experiments, should $T(n,m)$ be 1 or $\infty$? – John L. Jun 8 '19 at 13:49
• @Apass.Jack It is defined on $\mathbb Z_{\geq 1}\times \mathbb Z_{\geq 1}$. In addition, I should have written "else if" in the second case; I edited my question respectively. Finally, are my experiments correct? How to prove it? – Dudi Frid Jun 8 '19 at 15:54

Let us prove that for $$m \geq 1$$, $$T(n,m) = \max(1, 2\lfloor \tfrac{m-1}{(n-1)!} \rfloor - 1).$$ (This is the same as your formula.)
If $$m \leq 2(n-1)!$$ then by definition $$T(n,m) = 1$$, and indeed $$\lfloor \tfrac{m-1}{(n-1)!} \rfloor \leq 1$$, showing that our formula also gives the value $$1$$. If $$m > 2(n-1)!$$, then $$T(n,m) = \min_{\substack{a,b \geq 1 \\ ab \leq (n-1)!}} T(n-1,a) + T(n-1,b) + T(n-ab).$$ Since $$ab \leq (n-1)!$$ also $$a,b \leq (n-1)!$$, and so $$T(n-1,a) = T(n-1,b) = 1$$. Therefore $$T(n,m) = 2 + \min_{\substack{a,b \geq 1 \\ ab \leq (n-1)!}} T(n,m-ab) = 2 + \min_{1 \leq c \leq (n-1)!} T(n,m-c).$$ We can prove inductively that $$T(n,m)$$ is monotone nondecreasing, and so $$T(n,m) = 2 + T(n,m-(n-1)!).$$ From here it's not too hard to prove the formula by induction.