2
$\begingroup$

I need to solve the following recurrence relation, where $T(n,m)$ is defined over $\Bbb N_+\times\Bbb N_+$.

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

Note: This question is highly related to my previous question here, since $ab\leq\max\limits_{1\leq c\leq n-1}{c!(n-c)!}=(n-1)!$

I guess that the minimum is obtained at $c=\lceil n/2\rceil,a=c!,b=(n-c)!$, but I don't know how to prove it.

The first 10 values of the first n's are:

$T(1,*)=1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\dots\\ T(2,*)=1, 1, 3, 5, 7, 9, 11, 13, 15, 17,\dots\\ T(3,*)=1, 1, 1, 1, 3, 3, 5, 5, 7, 7,\dots\\ T(4,*)=1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\dots$

Experiments show that

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

for $f(n,m)=m-2(n-1)!$, and for some $g$ whose first values are: 1, 1, 2, 4, 12, 48, 240. I guess that $$g(n)=\begin{cases}1 & \text{if }n<3,\\ 2(n-2)! & \text{otherwise.}\end{cases}$$

$\endgroup$
  • $\begingroup$ Can you explain where all these questions are coming from? Are we solving some exercise sheet? Writing your thesis? $\endgroup$ – Yuval Filmus Jun 9 at 8:23
  • $\begingroup$ It's neither an exercise sheet, nor my thesis: I am working on a rather complicated article in combinatorics for a while, since I don't have co-authors in my article I post here some stuff to get some help and to assure that my conclusions are correct $\endgroup$ – Dudi Frid Jun 9 at 8:30
  • 4
    $\begingroup$ After getting all this help, you will be having co-authors, namely people who helped you write the article. $\endgroup$ – Yuval Filmus Jun 9 at 9:24
  • $\begingroup$ Assume that $T(n,m)$ is defined on $\Bbb Z_{\ge1}\times\Bbb Z_{\ge1}$ as before. What is the value of $T(1,3)$? Since $3\not\le2(1-1)!$, we cannot apply the first rule. Since there is no $c$ such that $c\ge1$ and $c<1-1$, so $T(1,3)$ is the min of an empty set to be infinity. Is $T(1,3)$ infinity? $\endgroup$ – Apass.Jack Jun 12 at 8:55
  • $\begingroup$ It looks like $T(1,m)$ for $m\ge 3$ can be set to infinity or any value that is no less than 1 without affecting other values. $\endgroup$ – Apass.Jack Jun 12 at 10:52
4
+150
$\begingroup$

Summary

It is not true that the minimum can always be obtained at $c=\lceil n/2\rceil,a=c!,b=(n-c)!$. Here is the smallest counterexample, $$T(5,49) = T(1,1) + T(4,1) + T(5,48) = 3 \not=5=T(3,6)+T(2,2)+T(5,12).$$ Instead, the minimum can always be obtained at $c=1$, $a=1$, $b=2(n-2)!.$

The following neat formula conjectured in the question is correct. $$T(n,m)=\begin{cases} 1 & n=1 \text{ or }f(n,m)\leq 0,\\ 3+2\Big\lfloor\dfrac {f(n,m)-1}{g(n)}\Big\rfloor &\text{otherwise}, \end{cases}$$ where $f(n,m)=m-2(n-1)!$ and $g(n)=\begin{cases}1 &\text{if }n<3,\\ 2(n-2)! &\text{otherwise.}\end{cases}$

Observations

  1. $T(n,m)=1,$ if $n=1$ or $m\le 2(n-1)!$.
  2. $T(n,m)$ is nondecreasing with respect to $m$.
  3. $T(n,m)\ge3$ if $m\gt 2(n-1)!$.
  4. $T(2,m)=\begin{cases} 1 & m\le2,\\ 2m-3 & \text{otherwise}.\end{cases}$
  5. If $n=3,4,5$, then the conjectured formula is correct.
  6. The following proposition $p(n,j)$ is true for all $n\ge3$ and $j\ge0$. $$\text{If $n\ge3$ and $j=\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor$ for some $j\ge0$ and $m$, then $T(n,m)=3+2j.$}$$

The conjectured formula is the same as the combination of observations 1, 4, and 6.

All observations above except observation 6 can be proved easily, although observation 5 might take a while to sort out case by case.

Let $S(n,m,a,b,c)=T(c,a)+T(n-c,b)+T(n, m-ab)$. Then for $m\gt 2(n-1)!$, $T(n,m)= \min\limits_{a,b,c\geq 1,\ c\le\frac n2\\a\leq c!,\ b\leq(n-c)!}S(n,m,a,b,c).$ The reason why we can replace the condition $c\le n-1$ by $c\le \frac n2$ is that $(n,m,a,b,c)=(n,m,b, a, n-c)$.

Proof of observation 6 by well-founded induction

Here are the steps. Steps 1 and 2 are the induction bases while step 3 is the induction step.

  1. Suppose $j=\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor=0$, i.e., $2(n-1)!\lt m\le2(n-1)!+2(n-2)!$. Since $m\gt 2(n-1)$, $$T(n,m)\ge3.$$ On the other hand, $$T(n,m)\le S(n,m,1,2(n-2)!,1)=1+1+1=3.$$ So $T(n,m)=3$, i.e., $p(n,j)$ is true when $j=0$.

  2. Observation 5 says that $p(n,j)$ is true for $n=3,4,5$.

  3. Let $n\ge6$ and $j\ge1$. As induction hypothesis, suppose $p(x,y)$ is true for all $x\le n$ or $x=n$ and $y\lt j$, i.e., $T(x,y)=3+2\lfloor\frac{f(x,y)-1}{2(x-2)!}\rfloor$, which implies, by the definition of $\lfloor\cdot\rfloor$, $$(x-2)!(T(x,y)+2x-5)<y\le (x-2)!(T(x,y)+2x-3).$$

    We will prove that $p(n,j)$ is true, i.e., $T(n,j)\le 3+2j$.

Let $j=\lfloor\frac{f(n,m)-1}{2(n-1)!}\rfloor$ for some $m$.

Proof for $T(n,m)\le 3+2j$

By induction hypothesis, we know that $T(n, m-2(n-2)!)=3+2(j-1)$. Hence, $$T(n,m)\le S(n,m,1,2(n-2)!,1)=1 + 1 + T(n, m-2(n-2)!)=3+2j.$$

Proof for $T(n,m)\ge 3+2j$

Because $T(n,m)$ is nondecreasing with respect to $m$ (observation 2), we will assume $m=2(n-1)!+2(n-2)!j+1$, the smallest value possible such that $j=\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor.$

We will prove that $S(n,m,a,b,c)\ge 3+2j$ for all valid choices of $(a,b,c)$. The case when $c=1$ or $c=2$ is relatively easy. From now on assume $3\le c\le \frac n2$.

Let $A=T(c,a)$ and $B=T(n-c,b)$. The case when $A=1$ or $B=1$ is much easier to prove. Now assume $A,B\ge2$.

  • Since $c<n$, we have $a\le(c-2)!(A+2c-3)$.
  • Since $n-c<n$, we have $b\le(n-c-2)!(B+2n-2c-3)$.
  • Since $ab\ge1$, we have $\lfloor\frac{f(n,m-ab)-1}{2(n-2)!}\rfloor<j$, so we can apply induction hypothesis to yield the first equality below.

Since $T(n,m)$ is nondecreasing w.r.t $m$, $$\begin{aligned} &S(n,m,a,b,c)\\ &\ge A+B+T(n,m-(c-2)!(A+2c-3)\,(n-c-2)!(B+2n-2c-3))\\ &= A+B+3+ 2\lfloor\frac{f(n,m-(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3))-1}{2(n-2)!}\rfloor\\ &= 3+2j+ A+B +2\lfloor\frac{-(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3))}{2(n-2)!}\rfloor\\ &\gt 3+2j+ \frac{(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3)}{(n-2)!}(h(c,A,B)-1) \\ \end{aligned}$$

where $$h(n,A,B,c)=\frac{(A+B-2)(n-2)!} {(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3)}.$$ Since $n-c<n$, induction hypothesis yields the second equality below. $$\begin{aligned} B&=T(n-c,b)\le T(n-c, (n-c)!)\\ &=3+2(\frac{(n-c)(n-c-1)}2-(n-c-1)-1)\\ &=(n-c)(n-c-3)+3. \end{aligned}$$ Since $n\ge6$ and $c\ge3$, $(n-2)!\ge (n-2)(n-3)(n-4)(c-2)!(n-c-2)!.$
Since $n\ge6$, $c\le \frac n2$ and $A,B\ge2$, $(n-2)(A+B-2)\gt A+2c-3.$

$$\begin{aligned}h(n,A,B,c) &\ge\frac{(A+B-2)(n-2)(n-3)(n-4)}{(A+2c-3)(B+2n-2c-3)}\\ &\ge\frac{(n-3)(n-4)}{B+2n-2c-3}\frac{(n-2)(A+B-2)}{A+2c-3}\\ &\ge\frac{(n-3)(n-4)}{(n-c)(n-c-1)}\frac{(n-2)(A+B-2)}{A+2c-3}\\ &\gt1 \end{aligned}$$

So $S(n,m, a,b,c) \gt 3+2j.$

The proof is complete. By the way, the proof for $T(n,j)\le 3+2j$ shows that the minimum can always be obtained at $c=1,$ $a=1,$ $b=2(n-2)!.$

Exercises

Exercise 1. Prove the formula for $T(2,m)$.

Exercise 2. (Observation 5) Prove the formula for $T(3,m)$, $T(4,m)$, and $T(5,m)$. Hint, the proof of observation 6 above might be helpful.

Exercise 3. Let $T_1$ be defined over $\Bbb N_{+}\times\Bbb N_{+}$. $$T_1(n,m)=\begin{cases} 1, & n=1\text{ or }m\leq (n-1)!\\ \min\limits_{a,b,c\geq 1,\ c\le n-1\\a\leq c!,\ b\leq(n-c)!}T_1(c,a)+T_1(n-c,b)+T_1(n,m-ab), & \text{else} \end{cases}$$ Show that $$T_1(n,m)=\begin{cases} 1 & n=1 \text{ or }m\le (n-1)!,\\ 3+2\Big\lfloor\dfrac {m-(n-1)!-1}{(n-2)!}\Big\rfloor & \text{otherwise}.\end{cases}$$

$\endgroup$
  • $\begingroup$ "$T(n,j)\le 3+2j$" should have been "$T(n,m)\le 3+2j$" $\endgroup$ – Apass.Jack Jul 6 at 10:17

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.