Finding a function satisfying a certain inequality

Question

This is a continuation of this post where I tried to find a function $f(n)$ that would satisfy the induction step of an inductive argument and it was shown that such function does not exist.

Trying to fix the problem I've come up with a stronger inductive argument that now requires finding a more elaborate function.

More precisely I would like to find a function $f(n,k)$ such that the following relation would hold for any $0 \leq p \leq (n-2-l)/2$ and $l \leq k$, $l \leq (n-2)$

$$p + f(n-1, k-l+p) \leq f(n,k).$$

$k \geq 0$ can be bounded to anything as long as the induction step still works out.

Is there a function $f(n,k)$ that satisfies the above inequality such that $$f(n,0) \leq \frac{n^2-6n+6}{6}.$$

Notice that if we take $f(n,k) = n^2-k$, then this gives a solution, but I need the function $f(n,0)$ to be smaller.

Answer 1

I wrote a program, which results suggest that the minimal function $\{f(n.0)\}$ satisfying the initial inequality,is $$\{0,0,0,1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81,90,100,110,\dots\}$$ that is $$f(n,0)=\left\lfloor\frac{(n-1)^2}4\right\rfloor.$$

program p1413656;
const
 NN=150;
var
  f:array[0..NN,0..NN] of Integer;
  n,k,p,l,lmax,pmax:Integer;
  OFi:Text;
begin
assign(OFi,'1413656.txt');
rewrite(OFi);
for k:=0 to NN do f[0,k]:=0;
for n:=1 to NN do begin for k:=0 to NN do begin
f[n,k]:=0;
if k<=(n-2) then lmax:=k else lmax:=n-2;
 for l:=0 to lmax do begin 
 {I assumed $l\ge 0$, in the opposite case $f(1,0)$ may be infinite}
  pmax:=NN-k+l;
  if pmax>((n-2-l) div 2) then pmax:=((n-2-l) div 2);
  for p:=0 to pmax do if f[n,k]<p+f[n-1,k-l+p] then f[n,k]:=p+f[n-1,k-l+p];
 end;
write(OFi,f[n,k],' ');
end; writeln (OFi) end;
end.

Answer 2

It seems the following.

Provided $n\ge 2$ put $k=l=\left\lfloor\frac{n-2}3\right\rfloor$ and $p=\left\lfloor\frac{n-3}3\right\rfloor$. Then

$$\left\lfloor\frac{n-3}3\right\rfloor+f\left(n-1,\left\lfloor\frac{n-3}3\right\rfloor\right)\le f\left(n, \left\lfloor\frac{n-2}3\right\rfloor\right),$$

which should give a lower bound $f\left(n, \left\lfloor\frac{n-2}3\right\rfloor)\right)\ge\frac {n^2}{6}-O(n)$. Now put $k=l=0$ and $p=\left\lfloor\frac{n-3}3\right\rfloor$.

Then $$f(n,0)\ge p+f(n-1,p)\ge\frac {n^2}{6}-O(n).$$

More precisely. The proposed lower bound is not far from your upper bound $f(n,0) \leq \frac{n^2-6n+6}{6}$. Indeed, for $n\ge 7$ we have

$$f(n,0)\ge \left\lfloor\frac{n-3}3\right\rfloor+f\left(n-1, \left\lfloor\frac{n-3}3\right\rfloor\right)\ge$$ $$\left\lfloor\frac{n-3}3\right\rfloor+\left\lfloor\frac{n-4}3\right\rfloor+f\left(n-2, \left\lfloor\frac{n-4}3\right\rfloor\right)\ge$$
$$\left\lfloor\frac{n-3}3\right\rfloor+\left\lfloor\frac{n-4}3\right\rfloor+\dots+\left\lfloor\frac{4}3\right\rfloor+f(2,0)\ge$$

$$-\frac{1}3+\sum_{k=4}^{n-3}\frac{k-1}3\ge \frac{n^2-7n+4}6.$$