Solving recurrence relation with minimum and factorial

Question

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

• Yuval Filmus: Can you explain where all these questions are coming from? Are we solving some exercise sheet? Writing your thesis?
• Dudi Frid: 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
• Yuval Filmus: After getting all this help, you will be having co-authors, namely people who helped you write the article.
• 喜欢算法和数学: 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?
• 喜欢算法和数学: 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.

Answer 1

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

• 喜欢算法和数学: "$T(n,j)\le 3+2j$" should have been "$T(n,m)\le 3+2j$"