# Solving recurrence relation with minimum and factorial

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

• Can you explain where all these questions are coming from? Are we solving some exercise sheet? Writing your thesis? – Yuval Filmus Jun 9 at 8:23
• 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 – Dudi Frid Jun 9 at 8:30
• After getting all this help, you will be having co-authors, namely people who helped you write the article. – Yuval Filmus Jun 9 at 9:24
• 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? – Apass.Jack Jun 12 at 8:55
• 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. – Apass.Jack Jun 12 at 10:52

### 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)

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, we have $$a\le(c-2)!(A+2c-3)$$.
• Since $$n-c, 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, 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, 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$" – Apass.Jack Jul 6 at 10:17