1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Apass.Jack Jun 8 at 13:49
  • $\begingroup$ @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? $\endgroup$ – Dudi Frid Jun 8 at 15:54
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.