Functional Equation!

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Functional Equation!

G H J

Reveal topic tags

functional equation

L

G H BBookmark kLocked kLocked NReply

Source: 2025 TST 24

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

869 posts

#1 h Mar 29, 2025, 10:48 AM • 2 Y

Y by MS_asdfgzxcvb, luutrongphuc

Find all functions $f:\mathbb Z\to\mathbb Z$ such that $f$ is unbounded and
$2f(m)f(n)-f(n-m)-1$ is a perfect square for all integer $m,n.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7357 posts

DottedCaculator

#2 h Mar 29, 2025, 11:03 PM • 2 Y

Y by MS_asdfgzxcvb, Hoto_Mukai

Fixing $n-m$ , making $f(m)f(n)$ large, then swapping $m$ and $n$ implies $f$ is even. Substituting $m=n=0$ implies $2f(0)^2-f(0)-1=(f(0)-1)(2f(0)+1)$ is a square. When $m=0$ , $f(n)(2f(0)-1)-1$ is a square. When $m=n$ , $2f(n)^2-f(0)-1$ is a square. In the first case, we can set $f(n)=Ca_n^2+D$ for a finite number of fixed values of $C$ and $D$ . Then, plugging into the second implies $2(Ca_n^2+D)^2-f(0)-1$ is a square. This forms an elliptic curve. By Siegel's theorem on integral zeros, this is only possible if a perfect square polynomial divides $2(Cx^2+D)^2-f(0)-1$ , which implies either $2D^2=f(0)+1$ or $f(0)=-1$ . The first case contradicts $2f(n)^2-f(0)-1$ square, and the first case implies $2f(n)^2-2D^2$ is a square for some fixed $D$ . In addition, $(2D^2-2)(4D^2-1)=2(D-1)(D+1)(2D-1)(2D+1)$ must be a square. Then, $D$ must be odd, and each term is either a square, twice a square, three times a square, or six times a square. By inspection, at least one of $2(D-1)(2D-1)$ , $2(D-1)(2D+1)$ , $2(D+1)(2D-1)$ , and $2(D+1)(2D+1)$ is a perfect square. This implies $D=\pm1$ , so $f(0)=1$ . Therefore, $2f(n)^2-2$ and $f(n)-1$ must be perfect squares for all $n$ , so $f(n)-1$ and $2f(n)+2$ are perfect squares. This implies
$f(n)=\frac{(17+12\sqrt2)^{a_n}+(17-12\sqrt 2)^{a_n}}2.$ Let $\alpha=17+12\sqrt2$ and $\beta=17-12\sqrt2$ . The expression is equal to
$\frac{\alpha^{a_n+a_m}+\alpha^{a_n-a_m}+\alpha^{a_m-a_n}+\alpha^{-a_n-a_m}-\alpha^{a_{n-m}}-\alpha^{-a_{n-m}}-2}2.$
Replacing $m$ with $-m$ implies that $|a_{n+m}|\leq|a_n|+|a_m|$ . Note that $\frac{(3+2\sqrt2)^{a_n+a_m}-(3-2\sqrt2)^{a_n+a_m}}{\sqrt2}$ squared differs from this expression by $\frac{\alpha^{a_n-a_m}+\alpha^{a_m-a_n}-\alpha^{a_{n-m}}-\alpha^{-a_{n-m}}}2$ . In particular, we must have either $a_m-a_n=\pm a_{n-m}$ or $2|a_{n-m}|>a_n+a_m$ . If we fix $n-m$ and make $a_n$ and $a_m$ large, then $a_m-a_n=\pm a_{n-m}$ . Now, we show $a$ is linear. If $a_n$ is sufficiently large, then $a_{n+1}=a_n\pm a_1$ , and $a_{n+2}=a_n\pm a_1\pm a_1$ , but $a_{n+2}=a_n\pm a_2$ . If $a_2=0$ , this contradicts unboundedness, so $a_2=2a_1$ , and $2a_{n+1}=a_n+a_{n+2}$ . Now, take $a_n$ sufficiently large so $a_n=a_{n+k}\pm ka_1$ , which implies $a_k=ka_1$ , so $a_n=Cn$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5 posts

#3 h Apr 15, 2025, 12:56 AM

Y by

DottedCaculator wrote:

Fixing $n-m$ , making $f(m)f(n)$ large, then swapping $m$ and $n$ implies $f$ is even. Substituting $m=n=0$ implies $2f(0)^2-f(0)-1=(f(0)-1)(2f(0)+1)$ is a square. When $m=0$ , $f(n)(2f(0)-1)-1$ is a square. When $m=n$ , $2f(n)^2-f(0)-1$ is a square. In the first case, we can set $f(n)=Ca_n^2+D$ for a finite number of fixed values of $C$ and $D$ . Then, plugging into the second implies $2(Ca_n^2+D)^2-f(0)-1$ is a square. This forms an elliptic curve. By Siegel's theorem on integral zeros, this is only possible if a perfect square polynomial divides $2(Cx^2+D)^2-f(0)-1$ , which implies either $2D^2=f(0)+1$ or $f(0)=-1$ . The first case contradicts $2f(n)^2-f(0)-1$ square, and the first case implies $2f(n)^2-2D^2$ is a square for some fixed $D$ . In addition, $(2D^2-2)(4D^2-1)=2(D-1)(D+1)(2D-1)(2D+1)$ must be a square. Then, $D$ must be odd, and each term is either a square, twice a square, three times a square, or six times a square. By inspection, at least one of $2(D-1)(2D-1)$ , $2(D-1)(2D+1)$ , $2(D+1)(2D-1)$ , and $2(D+1)(2D+1)$ is a perfect square. This implies $D=\pm1$ , so $f(0)=1$ . Therefore, $2f(n)^2-2$ and $f(n)-1$ must be perfect squares for all $n$ , so $f(n)-1$ and $2f(n)+2$ are perfect squares. This implies
$f(n)=\frac{(17+12\sqrt2)^{a_n}+(17-12\sqrt 2)^{a_n}}2.$ Let $\alpha=17+12\sqrt2$ and $\beta=17-12\sqrt2$ . The expression is equal to
$\frac{\alpha^{a_n+a_m}+\alpha^{a_n-a_m}+\alpha^{a_m-a_n}+\alpha^{-a_n-a_m}-\alpha^{a_{n-m}}-\alpha^{-a_{n-m}}-2}2.$
Replacing $m$ with $-m$ implies that $|a_{n+m}|\leq|a_n|+|a_m|$ . Note that $\frac{(3+2\sqrt2)^{a_n+a_m}-(3-2\sqrt2)^{a_n+a_m}}{\sqrt2}$ squared differs from this expression by $\frac{\alpha^{a_n-a_m}+\alpha^{a_m-a_n}-\alpha^{a_{n-m}}-\alpha^{-a_{n-m}}}2$ . In particular, we must have either $a_m-a_n=\pm a_{n-m}$ or $2|a_{n-m}|>a_n+a_m$ . If we fix $n-m$ and make $a_n$ and $a_m$ large, then $a_m-a_n=\pm a_{n-m}$ . Now, we show $a$ is linear. If $a_n$ is sufficiently large, then $a_{n+1}=a_n\pm a_1$ , and $a_{n+2}=a_n\pm a_1\pm a_1$ , but $a_{n+2}=a_n\pm a_2$ . If $a_2=0$ , this contradicts unboundedness, so $a_2=2a_1$ , and $2a_{n+1}=a_n+a_{n+2}$ . Now, take $a_n$ sufficiently large so $a_n=a_{n+k}\pm ka_1$ , which implies $a_k=ka_1$ , so $a_n=Cn$ .

If we use Siegel's theorem, we can do a bit more by showing that there is no unbounded functions $f\colon \mathbb{Z}\rightarrow \mathbb{Z}$ such that
$Af(m)f(n)+Bf(n-m)+C$ is a perfect square for all integers $m,n$ , where $A,B,$ and $C$ are constant integers with $A$ nonperfect square, $\gcd(A,B)=1$ , and $B\neq 0$ .

Letting $m=0$ shows that $f(n)(Af(0)+B)+C$ is a perfect square. Note that $Af(0)+B\neq 0$ since $B\neq 0$ and $\gcd(A,B)=1$ . So $f(n)(Af(0)+B)+C=g(n)^2$ , where $g\colon \mathbb{Z}\rightarrow \mathbb{Z}$ . Hence $f(n)=\dfrac{g(n)^2-C}{D}$ , where $D=Af(0)+B$ .

Letting $m=n$ shows that $Af(m)^2+Bf(0)+C$ is a perfect square. Thus $A\left(\dfrac{g(n)^2-C}{D}\right)^2+Bf(0)+C$ is a perfect square for all $n\in \mathbb Z$ . Let $k=(Bf(0)+C)D^2$ . Then $A(g(n)^2-C)^2+k$ is a perfect square for all integers $n$ . Since $f$ is unbounded, $g$ is unbounded, which shows that the quartic curve $y^2=A(x^2-C)^2+k$ has infinitely many integeral points, which is impossible due to Siegel's theorem (we use the condition $A$ is not a perfect square here).
So there does not exist function $f$ .

This post has been edited 8 times. Last edited by SanFangMath, Apr 15, 2025, 4:31 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

14 posts

#4 h May 15, 2025, 8:02 AM

Y by

Any solution without applying advanced tools?The case $f(0)>0$ can be addressed by some little bit tedious calculation with Pell equation and inequality bounding since the ratio of adjacent terms is always bounded.What about the opposite case?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

132 posts

#5 h May 16, 2025, 10:09 AM

Y by

What is Siegel’s theorem and what is the contest “2025 TST”? Is it 2025 USATST?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

499 posts

#6 h May 16, 2025, 10:56 AM

Y by

It is 2025 China TST. For Siegel look here.

This post has been edited 2 times. Last edited by Miquel-point, May 16, 2025, 10:57 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a