Maximize $f(0)+\cdots+f(n-1)$ subject to $f(x)f(y) + f(x+y) \leq 1$

Question

Suppose $f:\mathbf{N} \to [0,1]$ satisfies $$f(x)f(y) + f(x+y)\leq 1\qquad(1)$$ for all $x,y$. Let $$d_n = \frac{1}{n} \sum_{x=0}^{n-1} f(x).$$ It is easy to prove that $$\limsup d_n \leq 1/\varphi,$$ where $1/\varphi$ is the positive solution to $t^2+t=1$. (Start with $(1)$, take an average and $\limsup$ in $x$, then in $y$.)

What's interesting is that it does not seem nearly so easy to bound $d_n$, without the $\limsup$, independently of $f$. Is it true that $$d_n \leq 1/\varphi + o(1),$$ where the $o(1)$ is independent of $f$?

This does seem to be true numerically. In fact it may even be that $f \equiv 1/\varphi$ is the unique maximizer of $d_n$ for each $n$.

Answer 1

This system seems simple enough to throw to a CAS or some optimizer for small $n$. The inequalities are sequential: once you have understood behaviour for $n$, you can add a few more constraints for $n+1$ and try to understand the expanded system. To illustrate, I use $x_n$ in place of $f(n)$.

The first round is to maximize $x_0$ subject to $x_0^2 + x_0 \leq 1$. This is solved by the original poster and results in $x_0 = 1/\phi$.

The next round ($n=2$) adds the constraint equivalent to $x_{n-1} \leq 1/(1+x_0)$, and a little calculus and checking of boundary conditions gives $x_1 + x_0$ is maximized at $x_1=x_0=1/\phi$.

With each increase of $n$, the additional constraints are of the form $x_n \leq 1-x_j x_{n-j}$. However, we can ignore those constraints and focus on maximizing $x_0 + x_n$, which again we get with $x_0=x_n=1/\phi$. So I am guessing $1/\phi$ is the best you can do for the average value. (This does not quite work. However, if you get a value early on that approaches $1/\phi$, then this impacts later values. More work needs to be done.)

Here is some more work. Let us suppose we have $n$ least that $x_n \gt 1/\phi$. Then we have all the $x_i \it 1/\phi$ for all $0 \leq i \lt n$, and we know by above that the sum of the first $n+1$ variables is at most $(n+1)/\phi$. In particular, if $x_n=1/\phi + \epsilon$, then $x_0 \lt 1/\phi \lt \epsilon$.

If we now consider $x_j = 1/\phi - \delta$ and $x_{n-j} = 1/\phi - \gamma$, the relevant inequality gives $\phi\epsilon \lt \gamma + \delta$, so for $n \gt 2$ we have the sum is less than $(n+1)/\phi$ by at least $(\phi -1)\epsilon$, and this is magnified for all $\lfloor n/2 \rfloor$ pairs. It remains to study the case when $x_1$ and perhaps when $x_2$ are greater than $1/\phi$.

Update 2018.12.28

This argument is pretty simple, and suggests that something similar might work for $f$ over lower bounded subsets of the rationals or reals.

One sees that constant $f$ with value $f \leq 1/\phi$ satisfies the system of inequalities, so the best we can hope for is that $d_n \leq c=1/\phi$. I will recoordinatize and set $e_n = f(n) - c$, and use $c$ to simplify the TeX. We have $cc + c = 1$ and can rewrite the functional relation as $e_j(c + e_{n-j})+ ce_{n-j} + e_n \leq 0$.

We will be interested in showing the sum of the $e_j$ is at most 0. Towards that we rewrite the inequality as $e_{n-j} + e_n \leq e_j(-c - e_{n-j}) + (1 - c)e_{n-j}$. If all the $e_k$ are nonpositive, we are done. Otherwise, pick $j$ least with $e_j \gt 0$, and let $n\geq j$ be least $n$ with $e_n \gt 0$. Then the first form of the equality will imply $e_{n+j} \lt 0$, and the second form shows $-c \leq e_{n-j} \lt e_{n-j} + e_n \lt 0$.

Now let $j$ be least with $e_j \gt 0$. For every $n$, either $e_n \leq 0$ or else $e_{n-j} + e_n\lt 0$. This implies that the finite sum $e_0 + e_1 + \cdots + e_n \leq 0$ for all choices satisfying all the inequalities.

Gerhard "That's How I See It" Paseman, 2018.12.22.

Answer 2

Gerhard Paseman's solution is correct, and shows that $f \equiv 1/\phi$ is the unique maximizer of $d_n$ for each $n\geq 0$. Just reproducing here in as few words as I can, for the purpose of succinctness.

Let $c = 1/\varphi$ be the positive solution to $c^2 + c = 1$. Let $m\geq0$ be minimal such that $f(m) \geq c$ (if there is no such $m$ then we can go home). From now on, the only thing we will use is

$$f(x) c + f(x+m) \leq 1. \qquad(*)$$

If $m = 0$ this immediately implies $f(x) \leq c$ for all $x$, so assume $m>0$.

Claim: For any $i < m$ and any $k \geq0$, the sum of $f$ over the arithmetic progression $\{i, i+m, i+2m, \dots, i+(k-1)m\}$ is at most $kc$. The inequality is strict for $k > 0$.

Prove this and we're done, by partitioning $\{1, \dots, n\}$ into such progressions.

Proof: Use induction on $k$. The case $k=0$ is trivial. The case $k=1$ follows from $i < m$. For $k > 1$, note by induction and $(*)$ that $$f(i) + \cdots + f(i + (k-3)m) \leq (k-2)c,$$ $$f(i) + \cdots + f(i + (k-2)m) < (k-1)c,$$ $$f(i + (k-2)m) c + f(i+(k-1)m) \leq 1.$$ Add these together with weights $c$, $c^2$, and $1$.