Problem A. 880. (April 2024)
A. 880. Find all triples \(\displaystyle (a,b,c)\) of real numbers for which there exists a function \(\displaystyle f\colon \mathbb{Z}^+ \to \mathbb{Z}^+\) satisfying \(\displaystyle af(n)+bf(n+1)+cf(n+2)<0\) for every \(\displaystyle n \in \mathbb{Z}^+\) (\(\displaystyle \mathbb{Z}^{+}\) denotes the set of positive integers).
Proposed by András Imolay, Budapest
(7 pont)
Deadline expired on May 10, 2024.
Let's call a triple of real numbers \(\displaystyle (a,b,c)\) nice, if they satisfy the condition of the problem, i.e. an appropriate function exists.
Case 1: \(\displaystyle c<0\).
We claim that \(\displaystyle (a,b,c)\) is nice for arbitrary \(\displaystyle a,b\in \mathbb{R}\). We have to show an appropriate function \(\displaystyle f\). Let's define its values consecutively, paying attention that after defining the value at \(\displaystyle n+2\) the \(\displaystyle n^{\text{th}}\) condition is satisfied. Let \(\displaystyle f(1)=f(2)=1\), and let's assume that \(\displaystyle f(1)\), \(\displaystyle f(2)\),..., \(\displaystyle f(n+1)\) is defined such that for every \(\displaystyle k\le n-1\) condition \(\displaystyle af(k)+bf(k+1)+cf(k+2)\) is satisfied. Now choose \(\displaystyle f(n+2)\) large enoguh so that \(\displaystyle |cf(n+2)|>af(n)+bf(n+1)\) is satisfied. This is possible since \(\displaystyle c\neq 0\), and since \(\displaystyle c<0\), the \(\displaystyle n^{\text{th}}\) condition is satisfied as desired.
Case 2: \(\displaystyle c=0\).
We claim that \(\displaystyle (a,b,c)\) is nice iff \(\displaystyle b<0\) or \(\displaystyle a+b<0\). In the former case we can define values \(\displaystyle f(n)\) consecutively so that \(\displaystyle f(n+1)\) is large enough to satisfy \(\displaystyle |bf(n+1)|>af(n)\), yielding an appropriate function. In the latter case (\(\displaystyle a+b<0\)), the constant 1 function satisfies the condition.
We have to prove that if \(\displaystyle b\ge 0\) and \(\displaystyle a+b\ge 0\), then no appropriate function exists. This is obvious for \(\displaystyle a\ge 0\), otherwise observe that
\(\displaystyle 0>af(n)+bf(n+1)=-a(f(n+1)-f(n))+(a+b)f(n+1).\)
Since \(\displaystyle (a+b)f(n+1)\ge 0\) and \(\displaystyle a<0\), \(\displaystyle f(n+1)-f(n)<0\), i.e. \(\displaystyle f\) is strictly monotonously decreasing, however, this is not possible for a function mapping the positive integers to the positive integers.
Case 3: \(\displaystyle c>0\).
Subcase 3.1: \(\displaystyle a\le 0\).
We claim that \(\displaystyle (a,b,c)\) is nice iff \(\displaystyle a+b+c<0\). If this is true, the constant 1 function clearly satisfies the condition. Now let's assume that \(\displaystyle a+b+c\ge 0\), and take the sum of the first \(\displaystyle n\) conditions:
\(\displaystyle af(1)+(a+b)f(2)+(a+b+c)\sum\limits_{i=3}^n f(i)+(b+c)f(n+1)+cf(n+2)<0.\)
Since \(\displaystyle a+b+c\ge 0\) and \(\displaystyle a\le 0\) also implies \(\displaystyle b+c\ge 0\), the third and the fourth addend is not negative, and since \(\displaystyle c>0\), the last addend is also positive. Thus only the first two addends can be non-positive, however, their values are fixed. Thus \(\displaystyle cf(n+2)<-af(1)-(a+b)f(2)\), and so \(\displaystyle f(n+2)\) is bounded from above (again using \(\displaystyle c>0)\). This means there are only finitely many possibilities for the value of \(\displaystyle af(n)+bf(n+1)+cf(n+2)\), and thus it has a largest possible negative value, \(\displaystyle t\). However, this means that the sum on the left hand side of our previous inequality is also at most \(\displaystyle nt\), which contradicts the fact that it must be at least \(\displaystyle af(1)+bf(2)\).
Subcase 3.2: \(\displaystyle a>0\).
Clearly \(\displaystyle b\ge 0\) means there is no appropriate function, therefore we assume \(\displaystyle b<0\) from here. We consider two more subcases.
Subcase 3.2.1: \(\displaystyle c\ge a\).
We claim that \(\displaystyle (a,b,c)\) is nice iff \(\displaystyle a+b+c<0\). In this case the constant 1 function is appropriate. If \(\displaystyle a+b+c\ge 0\), let's rearrange the original inequality:
\(\displaystyle 0>af(n)+bf(n+1)+cf(n+2)=a(f(n)-f(n+1))+c(f(n+2)f(n+1))+(a+b+c)f(n+1)\ge a(f(n)-f(n+1))+c(f(n+2)-f(n+1)).\)
Using notation \(\displaystyle g(n)=f(n+1)-f(n)\) we get that \(\displaystyle ag(n) > cg(n+1)\). Since \(\displaystyle c\ge a>0\), this implies that \(\displaystyle g\) is strictly monotonously decreasing. Since its values are integers, this means that \(\displaystyle g\) is negative from somewhere, and this implies that \(\displaystyle f\) is strictly monotonously decreasing from somewhere, and this is impossible (since its values are positive integers).
Subcase 3.2.2: \(\displaystyle a>c\).
This is the hardest of all the cases, and the argument could seem a bit of magic at first sight, so we'll show the intuition behind this idea. The key insight is to try exponential functions \(\displaystyle f(n)=s^n\). There are several reasons to consider these kind of functions: as it's well known from the theory of linear recursions, exponential functions will reduce our conditions to a single condition, namely \(\displaystyle a+bs+cs^2<0\). On the other hand, if we observe the sum from subcase 3.1 and assume \(\displaystyle a+b+c>0\), then it's intuitively clear that if the third addend is trumped by the fourth one, the function has to increase quite quickly. Now fixing \(\displaystyle a\) and \(\displaystyle c\) will provide an \(\displaystyle s\) where \(\displaystyle b\) is the largest possible: \(\displaystyle s=\sqrt{a}/\sqrt{c}\) will yield the largest \(\displaystyle b\) for which \(\displaystyle a+bs+cs^2=0\), and then \(\displaystyle b=-2\sqrt{ac}\). We hope that these considerations will make the following section easier to follow:
We will prove that \(\displaystyle (a,b,c)\) is nice iff \(\displaystyle b\le -2\sqrt{ac}\). Clearly if \(\displaystyle b'\le b\), then \(\displaystyle f\) verifying that \(\displaystyle (a,b,c)\) is nice will also verify the niceness \(\displaystyle (a,b,c)\), so in order to find \(\displaystyle f\) we will assume \(\displaystyle b=-2\sqrt{ac}\). Let \(\displaystyle s=\sqrt{a}/\sqrt{c}\). Since \(\displaystyle a\neq c\), \(\displaystyle a+b+c=a+c-2\sqrt{ac}=(\sqrt{a}-\sqrt{c})^2>0\). Let \(\displaystyle N\) be a positive integer satisfying \(\displaystyle \frac{a+c}{a+b+c}<N\) and let \(\displaystyle k\) be chosen such that \(\displaystyle s^k>N\) (\(\displaystyle a>c>0\) implies \(\displaystyle s>1\), therefore \(\displaystyle k\) exists). Now let \(\displaystyle f(n)=\lceil s^{n+k} \rceil - N\). It's obvious that its values are positive integers, so let's check that it satisfies our conditions. First observe that by the choice of \(\displaystyle b\) and \(\displaystyle s\)
\(\displaystyle a+bs+cs^2=a-2a+a=0.\)
Then
\(\displaystyle af(n)+bf(n+1)+cf(n+2)=a(\lceil s^{n+k} \rceil - N)+b(\lceil s^{n+k+1} \rceil - N)+c(\lceil s^{n+k+2} \rceil - N) \leq\)
\(\displaystyle \leq a(s^{n+k} +1- N)+b( s^{n+k+1} - N)+c( s^{n+k+2} +1 - N)=\)
\(\displaystyle =s^{n+k}(a+bs+cs^2)+(a+c)-(a+b+c)N=(a+c)-(a+b+c)N<0,\)
thus \(\displaystyle f\) satisfies the conditions.
Finally, we will prove that no appropriate function exists if \(\displaystyle b>-2\sqrt{ac}\). Let \(\displaystyle \varepsilon>0\) be defined as \(\displaystyle b=-2\sqrt{ac}+\varepsilon\). Substitute these into the functional inequalities, and use what we have already established: \(\displaystyle a = \sqrt{ac}\cdot s = cs^2\).
\(\displaystyle af(n)+bf(n+1)+cf(n+2)=ag(n)s^n+(\varepsilon-2\sqrt{ac})g(n+1)s^{n+1}+cg(n+2)s^{n+2}=\)
\(\displaystyle as^n(g(n)-2g(n+1)+g(n+2))+\varepsilon s^{n+1}g(n+1)<0.\)
Let \(\displaystyle h\) be defined as \(\displaystyle h(n)=g(n+1)-g(n)\). Let's divide by \(\displaystyle as^n\) and subtsitue \(\displaystyle h\) to get
\(\displaystyle h(n+1)<h(n)-\frac{\varepsilon s}{a}g(n+1).\)
It's clear that the values of \(\displaystyle g\) are positive, therefore we can see that \(\displaystyle h(n)\) is strictly monotonously decreasing. We would like to get something similar as in subcase 3.2.1, but we have a little bit more work to do.
If there exists \(\displaystyle k\) for which \(\displaystyle h(k)<0\), then for all \(\displaystyle l\ge k\) we have \(\displaystyle h(l)\le h(k) < 0\), therefore \(\displaystyle g(l+1)-g(k)=\sum_{i=k}^{l} h(i)\le (l-k+1)h(k)\). Choosing \(\displaystyle l\) to be large enough the right hand side can be arbitrarily small, thus \(\displaystyle g(l+1)<0\) which is impossible. Now assume that no such \(\displaystyle k\) exists. This means that \(\displaystyle g\) is increasing, therefore \(\displaystyle g(n+1)\ge g(1)\) for all \(\displaystyle n\). However, this implies
\(\displaystyle h(n+1)<h(n)-\frac{\varepsilon s}{a}g(1), \)
where \(\displaystyle \frac{\varepsilon s}{a}g(1)\) is a positive constant, therefore each subsequent value of \(\displaystyle h\) decreases by a fix positive value, and thus it will be negative for a large enough value, which contradicts our assumption. This finishes our proof.
Statistics:
5 students sent a solution. 7 points: Szakács Ábel, Varga Boldizsár, Wiener Anna. 4 points: 1 student. 0 point: 1 student.
Problems in Mathematics of KöMaL, April 2024