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



Maximize $f(0)+\cdots+f(n-1)$ subject to $f(x)f(y) + f(x+y) \leq 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.


