Find all functions $f:\mathbb N_+\to \mathbb N_+,$ such that for all positive integer $a,b,$ $$\sum_{k=0}^{2b}f(a+k)=(2b+1)f(f(a)+b).$$ Created by Liang Xiao, Yunhao Fu
Problem
Source: 2024 CTST P5
Tags: algebra, functional equation, 2024 CTST
07.03.2024 08:03
Solved with megarnie, MathLuis, sixoneeight was trolling. We claim that constant $f(x)$ and $f(x) = x$ work. Denote the assertion with $P(a, b)$. By comparing $P(a+1, b)$ and $P(a, b)$, it follows that \[ f(a + 2b + 1) - f(a) = (2b + 1) (f(f(a + 1) + b) - f(f(a) + b)). \]Note that this implies that $f(x + p) \equiv f(x) \pmod{p}$. Claim: There exists a $t$ such that $f(a + t) > f(a)$ eventually. Proof. Note that \begin{align*} f(c) + \dots + f(2b + c - 2f(c)) &= (2b - 2f(c) + 1) f(b) \\ f(d) + \dots + f(2a + d - 2f(d)) &= (2a - 2f(d) + 1) f(a) \end{align*}follows by $P(c, b - f(c))$ and similar. Now, we can set $2b - 2f(c) = 2a - 2f(d)$ to get the result with $t = f(c) - f(d)$. Set $c = d + 1$, it either follows that the inequality holds, or that $f$ is the same value infinitely many times because $2b - f(c) + 1$ divides a constant term. $\blacksquare$ Claim: $f$ is constant if it is bounded. Proof. Take $\pmod{P}$ for a large prime $P$ which gives constant. $\blacksquare$ Claim: $f$ is $t$-injective for some $K$. Proof. Suppose that $f(c) = f(d)$. Then it follows that $c \not\equiv d \pmod{t}$, so this value occurs at most $Nt$ times $\blacksquare$ Claim: There exists a $t$ such that $f(a + t) = f(a) + k$ when sufficiently large. Proof. Note that \begin{align*} f(c) + \dots + f(2b + c - 2f(c)) &= (2b - 2f(c) + 1) f(b) \\ f(d) + \dots + f(2a + d - 2f(d)) &= (2a - 2f(d) + 1) f(a) \end{align*}follows by $P(c, b - f(c))$ and similar. Now, we can set $2b + c - 2f(c) = 2a + d - 2f(d)$ to get that \[ (2a + k_1) f(b) - (2a + k_2) f(a) \]is constant. This can only hold if $f(b) - f(a)$ is constant. $\blacksquare$ Note that $k$ must be divisible by $t$, so let $k = m \cdot t$. Claim: $m = 1$. Proof. It evidently follows that $m \ge 2$. Then consider $P(a, b)$ and $P(a + t, b)$ when sufficiently large to get that $(2b + 1) \cdot m = (2b +1) \cdot m^2$. $\blacksquare$ Claim: We must have that $t = 1$. Proof. Note that we have that $f(x + p) \equiv f(x) \pmod{p}$. Now, let $P = 1 + nt$ be a large prime. It follows that $p$ divides $nt + f(x + 1) - f(x)$, or that $f(x + 1) - f(x) \equiv 1 \pmod{p}$. Dirichlet's gives up infinitely many $p$ so $t = 1$. $\blacksquare$ Now, let $f(x) = x - T$ when sufficiently large. Applying the claim when sufficiently large gives that $(2b + 1)(a + b -T) = (2b + 1)(a + b - 2T)$ so $T = 0$. We can then use the interval fact to extend from $f(x) \ge x$ for $x \ge N$ to $x \ge 1$.
07.03.2024 08:08
i was NOT trolling, I actually helped
07.03.2024 12:01
07.03.2024 16:51
I believe this is a more enlightening but less magical solution. The answer is $f(x)=x$ and $f \equiv c$, which clearly work. Note the given assertion basically states that the average of $f(a)$ through $f(a+2b)$ equals $f(f(a)+b)$. Let $P(a,b)$ denote the assertion. Claim: If $f$ is unbounded, then it is injective; else $f$ is constant. Proof: If $f$ is unbounded but $f(p)=f(q)$ for some $p<q$, then by comparing $P(p,b)$ and $P(q,b)$ we find that for all $b$ we have $$f(p)+\cdots+f(p+2b)=f(q)+\cdots+f(q+2b) \implies f(p)+\cdots+f(q-1)=f(p+2b+1)+\cdots+f(q+2b).$$If $q-p>1$ then as $b$ varies, $f(t)$ appears on the RHS for all sufficiently large $t$, so the RHS is unbounded but LHS is not. If $q-p=1$ then we have $f(p)=f(p+2b+1)$ and thus can replace $q$ with $p+2b+1$ so that $q-p>1$ and repeat the previous argument. On the other hand, if $f$ is bounded, then let $M=\limsup_{x\to \infty} f(x)<\infty$. Pick $N \gg 1$ such that $x \geq N \implies f(x) \leq M$. Then fix $a \geq N$ and pick some $b$ with $b \geq N+1000$ and $f(f(a)+b)=M$. If $f(f(a)+b-1)<M$ then we find that $f(a+2b-1)+f(a+2b)$ must have average larger than $M$, but this contradicts the definition of $N$. Thus $f(f(a)+b-1)=M$, so by picking large $b$ and repeating this we find that $f$ is eventually constant. Then if $N'>1$ is the minimal integer such that $x \geq N' \implies f(x)=M$, from $P(N'-1,N')$ implies that $f(N'-1)=M$ as well; contradiction. Thus $f \equiv M$, i.e. $f$ is constant. $\blacksquare$ Since all constant solutions work, henceforth assume $f$ is injective. Lemma: For general $g : \mathbb{Z}^+ \to \mathbb{Z}^+$, if we fix $p>q$ then $g(p+b)\geq g(q+b)$ infinitely often. Proof: If there exists some $M$ such that $b \geq M \implies g(p+b)<g(q+b)$, then by taking $b=M,M+(p-q),M+2(p-q),\ldots$ we find $$g(q+M)>g(p+M)>g(2p-q+M)>g(3p-2q+M)>\cdots,$$and all of these inputs are positive, but this is absurd. $\blacksquare$ By injectivity, this lemma applied to $f$ yields $f(p+b)>f(q+b)$ infinitely often. Claim: $f$ is strictly increasing. Proof: Fix a choice of $a$ and compare $P(a,b)$ with $P(a+1,b)$ to get $$f(a+2b+1)-f(a)=(2b+1)(f(f(a+1)+b)-f(f(a)+b)).$$If $f(a+1)<f(a)$ (injectivity means $f(a+1)=f(a)$ is impossible) then the lemma implies the existence of infinitely many $b$ with $f(f(a)+b)>f(f(a+1)+b) \implies f(a)>f(a+2b+1)$. But this clearly contradicts injectivity. $\blacksquare$ To finish, observe that $P(a,1)$ implies $f(f(a)+1)$ is the average of $f(a),f(a+1),f(a+2)$. Since $f$ is increasing this implies $f(a) \leq a$, and by injectivity and induction we have $f(a)=a$ for all $a$. $\blacksquare$
08.03.2024 05:16
Hmm I think I found a different solution that's mostly NT, not sure if it works The only solutions are $\boxed{f(x) = x}$ and $\boxed{f\equiv c}$ for some constant $c$. These work, now we prove they are the only solutions. $P(a+1, b) - P(a,b): f(a + 2b + 1) - f(a) = (2b + 1) (f(f(a + 1) + b) - f(f(a) + b))$. Claim: For any odd prime $p$, we have $f(a+p) \equiv f(a) \pmod p$. Proof: This is obvious by choosing $2b + 1 = p$. $\square$ Therefore, the residue of $f(x)$ modulo $p$ is determined by the residue of $x$ modulo $p$. Claim: $f(f(x)) = f(x)$ for all positive integers $x$. Proof: Let $p$ be an odd prime and consider plugging $b \equiv 0\pmod p$ into $P(a+1, b) - P(a,b)$ and get\[ f(a+1) - f(a) \equiv f(f(a+1)) - f(f(a)) \pmod p,\]implying that $f(f(a)) - f(a) \equiv f(f(a+1)) - f(a+1)$ modulo $p$, so $f(f(x)) - f(x)$ is constant modulo $p$. Consider any positive integers $x,y$. Notice that for infinitely many primes $p$ we have that $f(f(x)) - f(x) \equiv f(f(y)) - f(y) \pmod p$, so $f(f(x)) - f(x) = f(f(y)) - f(y)$, meaning that $f(f(x)) = f(x) + c$ for some constant $c$ and all positive integers $x$. Suppose that $c\ne 0$. Let $p> c$ be an odd prime. We see that if $a$ is in the of $f$ in modulo $p$, then $a + c$ also is, so $a + nc$ is for any positive integer $n$. Since $\gcd(p,c) = 1$, $a + nc$ takes every residue modulo $p$, so every residue modulo $p$ is in the image of $f$. Now for any $x$, if $r$ is the number with $r\equiv x\pmod p$ and $r$ in the image of $f$, we have $f(r) = r + c$ and $f(x) \equiv f(r) \pmod p$, so $f(x) \equiv x + c\pmod p$ for all positive integers $x$, so $f(x) - x\equiv f(y) - y \pmod p$ for positive integres $x,y$. Therefore infinitely many primes $p$ satisfy $p\mid f(x) - x - (f(y) - y)$ for any $x,y$, so $f(x) = x + c$ for some constant $c$ and all positive integers $x$. $P(a,1): f(a) + f(a+1) + f(a+2) = 3 f(f(a) + 1)$, so $3a + 3 + 3c = 3 (a + 1 + 2c)$, so $c = 0$, contradiction. Therefore, we must have $c =0 $ and $f(f(x)) = f(x)$. $\square$ Case 1: $f$ is bounded. Let $M$ be the maximum possible value of $f$ and consider any distinct primes $p,q > 1434M + 23423589$. We have $p\mid f(x+p) - f(x)$ and $|f(x+p) - f(x)| < 2M+ 1< p$, meaning that $f(x+p) - f(x) = 0$ for any positive integer $x$. Similarly, we have $f(x+q) - f(x) = 0$. Let positive integers $m,n$ satisfy $m \cdot p - n \cdot q = 1$ (must exist since $p,q$ are relatively prime). We have $f(x) = f(x + p) = \cdots = f(x + mp)$ and\[f(x) = f(x + q) = \cdots = f(x + nq) = f(x + mp - 1)\]meaning that for all $C > mp$, we have $f(C) = f(C + 1)$, so $f$ is eventually constant (say at $c$). Suppose $f$ wasn't constant. Let $t$ be the largest positive integer such that $f(t) \ne f(t+1)$. From $P(t,t)$ we have $f(t) + f(t +1) + f(t+2) + \cdots + f(3t) = (2t+1) f(f(t) + t) $. The LHS clearly simplifies to $f(t) + 2t \cdot c$ and the RHS simplifies to $(2t+1) c$, so $f(t) = c$, absurd. Hence $f$ is constant. Case 2: $f$ is unbounded. Claim: For any $x,y$ with different parity, we have $x-y \mid f(x) - f(y)$. Proof: Consider some $x,y$ with different parity. WLOG $x>y$. It suffices to show that $\nu_p(x-y) \le \nu_p(f(x) - f(y))$. Indeed if we let $a = y$ and $2b + 1= x-y$ in $P(a+1, b) - P(a,b)$, we get that if $p^k \mid x-y$, then $p^k \mid f(x) - f(y)$, as desired. $\square$ Claim: There exists some parity such that infinitely many numbers of that parity are fixed points. Proof: Since $f$ is unbounded and $f(x)$ is a fixed point, there are infinitely many fixed points, so clearly some parity has infinitely many fixed points. $\square$ Let $S$ and $T$ denote the two parities (so one of them is the set of odds and the other is the set of evens), where $S$ has infinitely many fixed points. Choose $x$ as a fixed point in $S$ and $y\in T$ (clearly $x$ and $y$ have different parity). We have\[x - y \mid x - f(y)\implies x - y \mid y - f(y)\]Since $S$ has infinitely many fixed points, we can choose $x$ sufficiently large so that\[y - f(y) = 0\implies f(y) = y\forall y\in T\]Similarly, we can choose $x\in S$ and $y\in T$ and get\[ x - y \mid f(x) - y \implies x - y \mid x - f(x)\]Choosing $y$ sufficiently large gives that $f(x) = x$. Therefore $f(x) = x$ for all positive integers $x$, and we are done.
08.03.2024 05:51
$f(x)=C$ works since both sides are equal to $(2b+1)C$. Suppose $f$ is nonconstant. Taking mod $2b+1$ implies $\sum_{k=0}^{2b}f(a+k)\equiv0\equiv\sum_{k=0}^{2b}f(a+1+k)\pmod{2b+1}$, so $f(a)\equiv f(a+2b+1)\pmod{2b+1}$. If $f(x)<N$ is bounded, then $2N+1\mid f(x+2N+1)-f(x)$ and $2N+3\mid f(x+2N+3)-f(x)$, so $f(x)=f(x+2N+1)=f(x+2N+3)$. Since $\gcd(2N+1,2N+3)=1$, this implies $f$ is constant, contradiction. Therefore, $f$ is unbounded. If $f(x)=f(y)$, then $\sum_{k=0}^{2b}f(x+k)=\sum_{k=0}^{2b}f(y+k)$, so $\sum_{k=0}^{y-x-1}f(x+k)=\sum_{2b-y+x+1}^{2b}f(y+k)$. If $y-x-1>0$, then $f$ is bounded, contradiction. If $y-x-1=0$, then $f(x)=f(y+2b)$, so $y+2b-x>1$, contradiction. Now, $f$ is injective. Substitute $b$ odd, so $\sum_{k=0}^{2b}f(a+k)\equiv f(f(a))\pmod b$. We also get $\sum_{k=0}^{4b}f(a+k)\equiv f(f(a))\pmod b$, so $\sum_{k=2b+1}^{4b}f(a+k)\equiv f(f(a))\pmod b$, which means $\sum_{k=1}^{2b}f(a+2b+k)\equiv0\equiv f(f(a+2b))\pmod b$. Therefore, $f(a+2b)\equiv f(f(a+2b))\pmod b$, which implies $f(a)\equiv f(f(a))\pmod b$ for all odd $b$. This implies $f(a)=f(f(a))$, so $f(a)=a$ for all $a$, which works.
08.03.2024 15:21
08.03.2024 20:23
Nice problem! The only solution is $f \equiv id$ and $f \equiv c$ for some constant $c$. Assume $f$ non constant now. It is easy to see that $2b+1 \mid f(a+2b+1)-f(a)$, next we note that if $f$ is bounded, say $f < M$ then $2M+1 \mid f(x+2M+1)-f(x),$ $ 2M+3 \mid f(x+2M+3)-f(x)$ so $f(x)=f(x+2M+1)=f(x+2M+3)$ so $f$ is constant, contradiction. Now we claim $f$ is injective, assume not, say $f(i)=f(j)$ with $j > i$ then $\sum_{k=0}^{2b} f(i+k) = \sum_{k=0}^{2b} f(j+k)$ so $\sum_{k=0}^{j-i-1} f(i+k) = \sum_{k=2b-j+i+1}^{2b} f(j+k)$ now if $j-i > 1$ then $f$ is bounded contradiction. If $j=i+1$ then $f(i)=f(i+2b+1)$ and therefore we arrive at a contradiction again. So subsi $b$ odd in original equation to get $\sum_{k=0}^{2b} f(a+k) \equiv f(f(a)) (\mod b)$, also $\sum_{k=0}^{4b} f(a+k) \equiv f(f(a))$ and so $f(f(a+2b)) \equiv f(a+2b)$ and so $f$ is idempotent and by injectivity it must be identity.
15.03.2024 13:24
Easy one
09.04.2024 08:52
Related problem: 2015ISL N8, because for any $x-y$ is odd, we have $x-y|f(x)-f(y)$, So either $f$ has at least the order of a quadratic polynomial, or $f$ is almost linear
15.06.2024 19:00
My solution: (hidden because of length)
13.07.2024 10:26
The solutions are $f \equiv c$ and $f \equiv x$ which clearly work. Denote the assertion by $P(a,b).$ Comparing $P(a+1,b)$ and $P(a,b)$ gives that $f(a+2b+1) \equiv f(a) \pmod {2b+1}.$ Claim: If $f$ is unbounded, then $f$ is injective; else $f$ must be constant. Proof. Assume $f$ is unbounded and $f(p) = f(q)$ for some $p < q.$ Then for large enough $b$, $P(p,b)$ and $P(q,b)$ we have \[f(p) + \cdots + f(p+2b) = f(q) + \cdots + f(q+2b) \implies f(p) + \cdots + f(q-1) = f(p+2b+1) + \cdots + f(q+2b).\] Notice that if $p-q > 1$ LHS is bounded but RHS is not. If $p = q+1$ then, we can repeat the argument with $P(a,p)$ and $P(a,p+2b+1).$ Thus, if $f$ is unbounded, it must be injective. Now, if $f$ is bounded then as $$f(a+2b+1) \equiv f(a) \pmod {2b+1}$$ for sufficiently large $b$ we must have $f(a) = f(a+2b+1).$ That is $f(a) = f(a+2)$ for all $a$ by shifting $b \rightarrow b+1$ and $a \rightarrow a+2$. Now take $a$ to be odd then \[f(a) + f(a+1) + \cdots + f(a+2b) = (2b+1) f(f(a) + b) \implies (b+1)f(a) + bf(a+1) = (2b+1) f(f(a)+b).\] Now take $b$ to be opposite parity of $f(a)$ to get \[(b+1)f(a) + bf(a+1) = (2b+1)f(a)\] which implies $f(a) = f(a+1)$ for all $a$ odd. That is $f$ must be constant as claimed. Claim: $f$ is strictly increasing. Proof. It suffices to show that $f(m+1) > f(m)$ for all $m.$ Assume the contrary. Then $P(m+1,b) - P(m,b)$ implies \[(f(f(m+1)+b) - f(f(m)+b))(2b+1) = f(m+2b+1) - f(m).\] Note that $f(m+2b+1) > f(m)$ for infinitely many $b.$ Otherwise $f(m) > f(m+2b+1)$ infinitely often which contradicts injective. So for all large enough $b$ we must have \[f(f(m+1)+b) > f(f(m)+b).\] Let $d = f(m) - f(m+1) > 0.$ Which means for all large enough $K$ we must have $f(K) > f(K+d)$. But this means \[f(K) > f(K+d) > f(K+2d) > \cdots\] which is a contradiction as all the expressions are positive integers, proving the claim. Now to finish, note that $P(a,1)$ gives us that \[3 f(a) < f(a) +f(a+1) + f(a+2) = 3f(f(a) + 1) \implies f(a) < f(f(a)+1) \implies f(a) + 1 > a \implies f(a) \geq a.\] Similarly, \[3f(a+2) > 3 f(f(a) + 1) \implies f(a+2) > f(f(a)+1) \implies f(a) < a+1 \implies f(a) \leq a\] so $f(a) = a$ for all $a \in \mathbb{N}$ as claimed.
20.07.2024 19:08
EthanWYX2009 wrote: Find all functions $f:\mathbb N_+\to \mathbb N_+,$ such that for all positive integer $a,b,$ $$\sum_{k=0}^{2b}f(a+k)=(2b+1)f(f(a)+b).$$ Let $P(a,b)$ be the assertion of $\sum_{k=0}^{2b}f(a+k)=(2b+1)f(f(a)+b)$ Starting from trivial observations: Notice that $\sum_{k=0}^{2b}f(a+k) \equiv 0 \pmod {2b+1}$ $\implies$ $\sum_{k=0}^{n-1}f(a+k) \equiv 0 \pmod n$ $\forall n \in odd$ replace $a$ by $a+1$ $\implies$ $\sum_{k=0}^{n}f(a+k+1) \equiv \sum_{k=1}^{n+1}f(a+k) \equiv 0 \pmod n$ $\forall n \in odd$ subtract the above two equations $\implies$ $f(a+n) \equiv f(n) \pmod n$ $\forall n \in odd$ Case 1. $\exists$ $u < v$ such that $f(u)=f(v)$ $P(u,b)-P(v,b)$ $\implies$ $\sum_{k=0}^{2b}f(u+k)=\sum_{k=0}^{2b}f(v+k)$ $\forall b \in \mathbb N_+$ pick $b$ suffi large such that $u+2b>v$ for the above equation it's easy to see $f$ is bounded $\therefore \exists N \in \mathbb N_+$ such that $f(x) \leq N$ $\forall x \in \mathbb N_+$ From we know (1) $f(x+2N+1) \equiv f(x) \pmod {2N+1}$ $\overset{f(x)<2N+1}{\implies}$ $f(x+2N+1)=f(x)$ so $f$ is a periodic function with $T=2N+1$ (2) $f(x+2N+3) \equiv f(x) \pmod {2N+3}$ $\overset{f(x)<2N+3}{\implies}$ $f(x+2N+3)=f(x)$ so $f$ is a periodic function with $T=2N+3$ since $gcd(2N+1,2N+3)=1$ so $f$ is a constant. $\implies$ $\boxed{\text{S1 : }f(x)=c\quad\forall x}$(where c is an abritary $\mathbb N_+$) (which indeed work since $LHS=(2b+1)c=RHS$) Case 2. $f$ is injective choose $b \in odd$ consider $P(a,b)$ module $b$ and applying $LHS=\sum_{k=0}^{2b}f(a+k)=f(a)+(f(a+1)+...+f(a+b))+(f(a+b+1)+...+f(a+2b)) \equiv f(a)+2 \times (\text{complete residue system})\equiv f(a) \pmod b$ $RHS=(2b+1)f(f(a)+b) \equiv f(f(a)+b) \equiv f(f(a)) \pmod b$ $\therefore$ $b|f(a)-f(f(a))$ $\forall b \in odd$, pick $b \rightarrow \infty$ we know $f(f(a)-a)$ has infinity odd divisors which means $f(a)-f(f(a))=0$ $\overset{inj.}{\implies}$ $f(a)=a$ so we get $\boxed{\text{S2 : }f(x)=x\quad\forall x}$ (which indeed work since $LHS=\sum_{k=0}^{2b}(a+k)=(2b+1)a+\frac{2b(2b+1)}{2}=(2b+1)(a+b)=(2b+1)f(f(a)+b)=RHS$)