Let $T(n,m)=\frac { n^2\cdot m\cdot f(n)}{n!}$.
I need to find $f$ in terms of $n$, such that:
- $f$ is non decreasing function
- $f(n)\in\Omega(1)$
- $\exists k>0.\ f(n)\in O(n^k)$
- The following statement would be true:
$\forall n,m\begin{cases}n,m>0\\ m\leq n!\end{cases}\ \exists\ a,b,c.\ \begin{cases} T(n,m)=T(a,b)+T(n-a,c)+T(n,m-bc) \\ a,\ b,\ n-a,\ c,\ n,\ m-bc > 0 \\ b\leq a!,\ c\leq (n-a)!\end{cases}$
My efforts so far:
I created a python code and concluded that $f$ is neither a polynomial, nor a polygarithm, nor a product of polynomial and polygarithm.
Thus, I believe that the desired $f$ does not exist. However, I don't know how to disprove its exitence rigorously.
Help would be highly appreciated!
Edit: I came up with two lemmas that together yield that such a $f$ does not exist.
Lemma 1
Let us define $T_k(n,m):=\frac { n^2\cdot m\cdot n^k}{n!}$
Then,
$\forall k, n,m,a,b,c.\\ \begin{cases} \ k,\ n,\ m,\ a,\ b,\ n-a,\ c,\ n,\ m-bc > 0\ \\ b\leq a!,\ c\leq (n-a)!\end{cases} \\ \Rightarrow T_k(n,m) <T_k(a,b)+T_k(n-a,c)+T_k(n,m-bc)$
Lemma 2 $\forall f,g, x,y,a,b,c,d\begin{cases}\forall z. f(z)\geq g(z) \\ f\text{ is non-decreasing} \\ a,b,c<d \\ a+b+c>d \\ f(x)\cdot a+f(y)\cdot b+f(x+y)\cdot c>f(x+y)\cdot d\end{cases}\\ \Rightarrow g(x)\cdot a+g(y)\cdot b+g(x+y)\cdot c>g(x+y)\cdot d$
What's left?
Are these two lemmas correct? How should I prove them?