Let $\mathbb{N}$ denote the set of positive integers. Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ such that for positive integers $a$ and $b,$ \[f(a^2 + b^2) = f(a)f(b) \text{ and } f(a^2) = f(a)^2.\]
Problem
Source: 2021 USAJMO Problem 1
Tags: function, USAJMO, functional equation
15.04.2021 20:13
Claim: $f^2(m^2+n^2)=f(2mn)f(m^2-n^2)$ for all $m>n$. Proof: The RHS equals $f((m^2-n^2)^2+(2mn)^2) = f((m^2+n^2)^2)=f^2(m^2+n^2)$ hence done $\blacksquare$. Therefore $f(m)=f(n)=1$ implies $ f(2mn)=f(m^2-n^2)=1$ as well. Note that $f(1)=1$ by the first condition and $f(2)=1$ by the second. Now assume that for all integers $m$ up to $k \geq 2$, $f(m)=1$ holds. If $k+1 \equiv 2 \pmod 4$, take $m,n$ such that $2mn=k+1$ and note that $m,n \leq \frac{k+1}{2} <k$ so $f(m)=f(n)=1$ by the inductive hypothesis hence $f(2mn)=f(k+1)=1$, so we are done. If it is not $2 \pmod 4$ we may take $m>n$ such that $m^2-n^2=k+1$ and note that $$2n<2m=(m-n)+(m+n) \leq (m-n)(m+n)+1=k+2 \leq 2k,$$hence both $m,n$ are $\leq k$ so $f(m)=f(n)=1$ by the inductive hypothesis, therefore again $f(m^2-n^2)=f(k+1)=1$. Thus, $f \equiv 1$ for all positive integers, which evidently satisfies, so it is our only solution.
15.04.2021 20:16
We claim the only solution to the equation is $\boxed{f(x) = 1}$. This works because: $$f(a^2+b^2) = f(a)f(b) \Rightarrow 1=1\cdot1$$$$f(a^2) = f(a)^2 \Rightarrow 1 = 1^2$$We will prove this using strong induction: Base Case: $n=1,2$ $$f(1^2) = f(1)^2$$$$f(1)\left(f(1) - 1\right) = 0$$However, since $0$ is not in $\mathbb N$, $f(1) = 1$. Now, plugging in $a=b=1$, into the first equation: $$f(2) = f(1)f(1) = 1$$ Inductive Step: Suppose $f(x) = 1$ for all integers $0<x<n$. Then, we will prove that $f(n) =1$. First, plug in $a=2uv$ and $b=u^2-v^2$ into the first equation: $$f(2uv)f(u^2-v^2) = f\left((2uv)^2 + (u^2-v^2)^2\right) = f((u^2+v^2)^2) = f(u^2+v^2)^2$$However, plugging in $a=u$ and $b=v$: $$f(u^2+v^2) = f(u)f(v)$$$$f(u)^2f(v)^2=f(u^2+v^2)^2$$This means that: \[ f(2uv)f(u^2-v^2) = f(u)^2f(v)^2 \tag{$\ast$} \] Now, we take casework on the parity of $n$: Case 1: $n$ is even Let $n=2k$. Then, plugging in $u=k$ and $v=1$ into $(\ast)$, $$f(2k)f(k^2-1)=f(k)^2f(1)^2$$Since $k<n$, by inductive hypothesis: $$f(n)f(k^2-1)=1$$However, since the range of $f$ is $\mathbb N$, both the terms on the left hand side have to be $1$. This means that $f(n)=1$, so we are done with this case. Case 2: $n$ is odd Let $n=2k+1$. Then, plugging in $u=k+1$ and $v=k$ into $(\ast)$, $$f(2k(k+1))f((k+1)^2-k^2)=f(k)^2f(k+1)^2$$$$f(2k(k+1))f(n)=f(k)^2f(k+1)^2$$Again, since $k,k+1<n$, by inductive hypothesis: $$f(2k(k+1))f(n) = 1$$Again, since the range of $f$ is $\mathbb N$, both the terms on the left hand side have to be $1$ which means that $f(n)=1$, so we are done with this case as well. Therefore, both cases yield $f(n)=1$, so we are done with our inductive step. Our induction covers the entire domain of $f$, so we can conclude that $f(x)=1$ is the only solution.
15.04.2021 20:27
15.04.2021 20:31
Was this possible without splitting into even/odd? I'm did something weird and now I don't know if it's legit.
15.04.2021 20:36
Feel like the induction idea is pretty standard. The only solution is $\boxed{f\equiv 1},$ which clearly works. To prove that $f(n)=1$ for all $n,$ we will induct on $n.$ $\emph{Base Case: }$ $n=1$ Plugging $a=1$ into the second assertion yields $f(1)=f(1)^2,$ so since $f(1)$ is a natural number, it must be $1.$ $\emph{Inductive Step: }$ Case 1: $n$ is odd Plugging $(a,b)=(n,\frac{n^2-1}{2})$ into the first assertion gives $$f\left(\frac{n^4+2n^2+1}{4}\right)=f(n)f\left(\frac{n^2-1}{2}\right).$$Since $\frac{n^4+2n^2+1}{4}=(\frac{n^2+1}{2})^2,$ the second assertion yields $$f\left(\frac{n^2+1}{2}\right)^2=f(n)f\left(\frac{n^2-1}{2}\right).$$On the other hand, by plugging $(a,b)=(\frac{n-1}{2},\frac{n+1}{2})$ into the first assertion, we obtain $$f\left(\frac{n^2+1}{2}\right)=f\left(\frac{n-1}{2}\right)f\left(\frac{n+1}{2}\right),$$which equals $1$ by the inductive hypothesis. Thus, $f(n)f\left(\frac{n^2-1}{2}\right)=1,$ forcing $f(n)=1.$ Case 2: $n$ is even and $n\ge 4$ Plugging $(a,b)=(n,\frac{n^2-4}{4})$ into the first assertion gives $$f\left(\frac{n^4+8n^2+16}{4}\right)=f(n)f\left(\frac{n^2-4}{4}\right).$$Since $\frac{n^4+8n^2+16}{16}=(\frac{n^2+4}{4})^2,$ the second assertion yields $$f\left(\frac{n^2+4}{4}\right)^2=f(n)f\left(\frac{n^2-4}{4}\right).$$On the other hand, plugging $(a,b)=(\frac{n}{2},1)$ into the first assertion, we get $$f\left(\frac{n^2+4}{4}\right)=f\left(\frac{n}{2}\right)f(1),$$which equals $1$ by the inductive hypothesis. Hence $f(n)f(\frac{n^2-4}{4})=1,$ so $f(n)$ must be $1.$ Case 3: $n=2$ Plugging $(a,b)=(1,1)$ into the first assertion gives $$f(2)=f(1)^2=1,$$as desired. Our proof is complete.
15.04.2021 20:58
Sketch: f \cong 1 get f(1)=f(2)=1 If f(n) =f(n-1)=1, then we have f(2n)=f(2n-1)=1 for all n ge 2 Hinges on (n^2 + 1)^2 = (n^2 -1)^2 + (2n)^2 and (2n^2 -2n+1)^2=(2n-1)^2 + (2n^2 - 2n)^2 Way too hard for a J1 imo
15.04.2021 21:05
This was hard especially for a j1. There are basically three steps: Step 1: prove $f(1)=f(2)=1$ (easy) Step 2: Prove that $f(a)=1 \implies f(2a)=1$ Step 3: Prove that $f(a)=f(a+1)=1 \implies f(2a+1)=1$. Then strong induction finishes. However neither step 2 nor step 3 are particularly easy to find, and it's hard to naturally "get" there without taking a fairly big leap of faith.
15.04.2021 21:09
vvluo wrote: Way too hard for a J1 imo you can say that again i wasted the whole 4.5 hours on this
15.04.2021 21:23
Very contrived . $f(1)=1$, $f(2)=1$. It can be confirmed that $f(k)=1$ for all $1\leq k\leq 13$. It suffices to show that for all $1\leq i\leq j$ such that $f(i)=1\implies f(j+1)=1$. Note that $(m+n)^2+(8m+3n)^2=(7m+3n)^2+(4m+n)^2$, and by Frobenius coin all integers greater than $13$ can be expressed as $8m+3n$, as desired.
15.04.2021 21:26
My solution was so weird... Proved that if f(x+1)=1, then f(x)=1. Then infinite values give f(y)=1, so we're done
15.04.2021 22:19
bump plsss sry idk my solution looks different so im thinking there is some error somewhere and idk where
15.04.2021 22:22
I claim the only answer is $\boxed{f(n)=1}$ for all $n\in\mathbb{N}$. It is easy to verify that this satisfies the problem conditions. First, note that $f(1)=1$ because $f(1)=f(1)^2$. Furthermore, $f(2)=1$ because $f(2)=f(1^2+1^2)=f(1)^2=1$. Observe that $$f\big((x^2-y^2)^2+(2xy)^2\big)=f\big((x^2+y^2)^2\big)=f(x^2+y^2)^2=f(x)^2f(y)^2$$$$f\big((x^2-y^2)^2+(2xy)^2\big)=f(x^2-y^2)f(2xy)$$$$\implies f(x)^2f(y)^2=f(x^2-y^2)f(2xy)\qquad (\clubsuit).$$In particular, if $f(x)=f(y)=1$, then by $(\clubsuit)$ we know that $f(x^2-y^2)=f(2xy)=1$. We now finish with strong induction. We have already shown our base cases: $f(1)=f(2)=1$. Now, assume that $f(k)=1$ for all $k\in[1,n]$. If $n+1$ is even, then by our inductive assumption, $f(1)=f\left(\frac{n+1}{2}\right)=1$, so by $(\clubsuit)$, $f\left(2\cdot1\cdot\frac{n+1}{2}\right)=f(n+1)=1$. If $n+1$ is odd, let $n=2k$. By our inductive assumption, $f(k)=f(k+1)=1$, so again by $(\clubsuit)$, $f\big((k+1)^2-k^2\big)=f(2k+1)=f(n+1)=1$. This completes the induction, so $f(n)$ is always equal to $1$.
15.04.2021 22:25
The $f(a^2)=a^2$ condition is not necessary. I will show $f(x)=1$ for every $x$, this works. Let $n\neq 1,2,3,4,5,6,8,10$. Then $n>\frac{n+3}{2},\frac{n-5}{2}>0$ if $n$ is odd and $n>\frac{n+6}{2},\frac{n-10}{2}>0$ if $n$ is even. For odd $n$ we have $n^2-(n-2)^2=(\frac{n+3}{2})^2-(\frac{n-5}{2})^2=4n-4$, so $f(n)f(\frac{n-5}{2})=f(n-2)f(\frac{n+3}{2})$. For even $n$ we have $n^2-(n-4)^2=(\frac{n+6}{2})^2-(\frac{n-10}{2})^2=8n-16$, so $f(n)f(\frac{n-10}{2})=f(n-4)f(\frac{n+6}{2})$. Thus for these $n$ strong induction works, we just have to bash out $n=1,2,3,4,5,6,8,10$. $1025=32^2+1^2=20^2+25^2,32=4^2+4^2,25=4^2+3^2,20=4^2+2^2$. This means $f(1025)=f(4)^2f(1)=f(4)^2f(2)f(3)$. However $f(2)=f(1)^2$, so $f(1)=f(2)=f(3)=1$. $f(5)=f(2)f(1),f(8)=f(2)^2=1,f(10)=f(3)f(1)=1$. $325=18^2+1^2=17^2+6^2,18=3^2+3^2,17=4^2+1^2$. This means that $f(325)=f(4)f(6)f(1)=f(3)^2f(1)=1$, so $f(4)=f(6)=1$, as desired. Edit: $n=8$ works from the identity also, just use $\frac{10-n}{2}$, but I was too lazy to point this out.
15.04.2021 22:28
My problem I wrote it a few years ago by trying to integrate the characterization of Pythagorean triples into an FE, because if $a^2+b^2=c^2$ then you get $f(a)f(b)=f(c)^2$. Picking the right triples $(a,b,c)$ then lets you induct to show $f\equiv 1$, as in many of the above solutions. Honestly a bit surprised it ended up as JMO #1 though, especially because nobody bothered to tell me the problem was accepted
15.04.2021 22:29
am I the only one that substituted a bunch of numbers and variables and don't know how to continue?
15.04.2021 22:37
tastymath75025 wrote: My problem What did you write it for originally? Was it realized during the testsolving process that $f(a^2)=f(a)^2$ isn't necessary (assuming my proof is right).
15.04.2021 22:43
i3435 wrote: tastymath75025 wrote: My problem What did you write it for originally? Was it realized during the testsolving process that $f(a^2)=f(a)^2$ isn't necessary (assuming my proof is right). It made the problem easier. Still unsuitable for j1 imo.
15.04.2021 23:36
i3435 wrote: tastymath75025 wrote: My problem What did you write it for originally? Was it realized during the testsolving process that $f(a^2)=f(a)^2$ isn't necessary (assuming my proof is right). yeah you're right, the condition is unnecessary, however I wouldn't have solved it without that condition - I wouldn't have realized there was a pythagorean property. Without this condition it probably would have been JMO 3/6
16.04.2021 01:17
SKeole wrote: i3435 wrote: tastymath75025 wrote: My problem What did you write it for originally? Was it realized during the testsolving process that $f(a^2)=f(a)^2$ isn't necessary (assuming my proof is right). yeah you're right, the condition is unnecessary, however I wouldn't have solved it without that condition - I wouldn't have realized there was a pythagorean property. Without this condition it probably would have been JMO 3/6 IMO (in my opinion) this is already harder than JMO 3
02.08.2023 01:36
mathmax12 wrote: we can proove by induction that f(x)=1 in the only solution okay dont put a sketch after so many solutions have been written. Honestly, not that bad for a P1, very well suited. First note that f(1)=1,f(2)=1. We proceed by strong induction with inductive hypothesis that all integers k<n we have f(k)=1. The reason for this is obvious, but the next few steps are well motivated because taking some $c^2=a^2+b^2\implies f(c)^2=f(a^2+b^2)=1$, which means all $(a,b,c)=(2mn,m^2-n^2,m^2+n^2)$ help a lot. (This decomposition of taking some f(c^2)=f((m^2-n^2)^2+(2mn)^2)=f(m^2-n^2)f(2mn) will come in useful later, and this simplification is omitted below!) Suppose n=2m. Notice $$f(m^2+1)=f(m)f(1)=1\implies 1=f(m^2+1)^2=f((m^2+1)^2)=f(m^2-1)f(2m)\implies f(n)=1,$$which implies the strong induction. $\square$ On the other hand, if n=2m+1, notice $$f(m^2+(m+1)^2)=f(m)f(m+1)=1\implies 1=f(m^2+(m+1)^2)^2=f((m^2+(m+1)^2)^2)=f(2((m+1)m)^2)f((m+1)^2-m^2)\implies f(n)=1,$$which finishes. $\blacksquare$
20.08.2023 04:40
We claim that $\boxed{f(x)=1}$, is the only function that works. Claim: $f^2(m^2+n^2)=f(2mn)f(m^2-n^2)$ Proof: It is obvious that $f((2mn)^2+(m^2-n^2)^2)=f((m^2+n^2)^2)=f^2(m^2+n^2)$, hence, proved. So $f(2mn)=f(m^2-n^2)=1.$ Now we use induction. The base case, always works. oops i cant continue, i cant do the rest
26.09.2023 19:50
We claim the only satisfactory functions are $f(x) \equiv 1$. It is easy to see this works. Let $P(a, b)$ denote the assertion for the equation $f(a^2 + b^2) = f(a)f(b)$ and $Q(a)$ denote the assertion for the second equation. Begin by noting from $Q(1)$ we have $f(1) = f(1)^2$, giving $f(1) = 1$. Now from a simple induction $f(2^k) = 1$ for all $k \geq 0$. Indeed, for odd $k$ take $P\left(2^{\frac{k-1}{2}}, 2^{\frac{k-1}{2}}\right)$, and for even $k$ take $Q\left(2^{\frac{k}{2}}\right)$. Now we prove the claim using strong induction. From $P(k^2+k, 2k + 1)$ gives, \begin{align*} f\left(\left((k+1)^2 + k^2\right)^2\right) &= f((k(k+1)) \cdot f(2k + 1)\\ f\left( (k+1)^2 + k^2 \right) ^2 &= f(k^2 + k) \cdot f(2k+1)\\ \left( f(k+1)f(k) \right)^2 &= f(k^2+k) \cdot f(2k+1)\\ 1 &= f(k^2+k) \cdot f(2k+1) \end{align*}Similarly from $P(2k + 2, k^2 + 2k)$ we have, \begin{align*} \left(f(k+1) \right)^2 &= f(2k+2) \cdot f(k^2 + 2k)\\ 1 &= f(2k+2) \cdot f(k^2 + 2k) \end{align*}It is now easy to see that we can show $f \equiv 1$ by solving for odd and even $x$ using the first and second equations respectively.
17.10.2023 09:03
We claim the answer is $\boxed{f(x)=1}$. We will show this using a claim: Claim: If $f(a)=f(b)=1$, $a>b$, we must have $f(a^2-b^2)=f(2ab)=1$ as well. Proof: We have \begin{align*} 1=f(a)f(b)&=f(a^2+b^2)=f((a^2+b^2)^2) \\ &= f((a^2-b^2)^2+(2ab)^2)=f(a^2-b^2)f(2ab) \end{align*} so we must have $f(a^2-b^2)=f(2ab)=1$. $\square$ We have $f(1)=f(2)=1$, so a simple induction finishes. If $n$ is even, write as $n=2k$, and plug in $(a,b)=(k,1)$, so that $2ab=n$. If $n$ is odd, write as $n=2k-1$, and plug in $(a,b)=(k, k-1)$ so that $a^2-b^2=n$.
17.12.2023 23:56
It's easy to get $f(1)=f(2)=1$. We can use our two conditions to get \[f(a) f(b) = \sqrt{f\left((a^2+b^2)^2\right)} = \sqrt{f\left((a^2-b^2)^2+(2ab)^2\right)} = \sqrt{f\left(a^2-b^2\right) f(2ab)}.\] Note that our function is over the natural numbers, so if $f(a)=f(b)=1$, then we immediately know $f\left(a^2-b^2\right)=f(2ab)=1$. We now use strong induction with our base cases 1 and 2 to show $f(x)=1$ for all natural $x$. Assume $f(1)=f(2)= \ldots = f(k-1)=1$ for an integer $k>2$, and we want to show $f(k)=1$. If $k$ is even: Substitute $\left(\frac k2, 1\right)$. If $k$ is odd: Substitute $\left(\frac{k+1}{2}, \frac{k-1}{2}\right)$. This alogirthm tells us $f(k)=1$ for all $k$, so our solution is $\boxed{f(x)=1}$, which clearly works.
31.12.2023 11:09
$f \equiv 1$ is the only solution. Note that $f(a^2) = f(a)^2$. Now by putting $a=1$, we get $f(1) = 1$. $f(2) = f(1^2 + 1^2) = f(1) \cdot f(1) = 1$. $f(4) = f(2^2) = f(2)^2 = 1$. $f(5) = f(1^2 + 2^2) = f(1) \cdot f(2) = 1$. Now note that $f(3^2 + 4^2) = f(5^2) \implies f(3)f(4) = f(5)^2 \implies f(3) = 1$. $f(8) = f(2^2+2^2) = f(2) \cdot f(2) = 1$. $f(10) = f(1^2 + 3^2) = f(1) \cdot f(3) = 1$. $f(6^2 + 8^2) = f(10^2) \implies f(6) = 1$. $f(7^2 + 24^2) = f(25^2) = f(5)^4 = 1\implies f(7) = 1$. Now we proceed by using strong induction. We show that $f(4k+1) = f(4k+2) = f(4k+3) = f(4k+4) = 1$. This would simply result in $f\equiv 1$. We have already prove our base cases for $k=0$ and $1$. Firstly, let $P(a,b)$ be the assertion for $f(a^2+b^2) = f(a)\cdot f(b)$. So for sone $m>n$, we have, \begin{align*} P(m^2-n^2,2mn) &\implies f((m^2-n^2)^2 + (2mn)^2) = f(m^2-n^2)\cdot f(2mn)\\ &\implies f((m^2+n^2)^2) = f(m^2-n^2)\cdot f(2mn)\\ &\implies f(m^2 + n^2)^2 = f(m^2 - n^2) \cdot f(2mn)\\ &\implies f(m)^2\cdot f(n)^2 = f(m^2 - n^2) \cdot f(2mn) .\end{align*} Denote the final equation above by the assertion $Q(m,n)$. $Q(2k+1,2k) \implies f(2k+1)^2 \cdot f(2k)^2 = f(4k+1)\cdot f(2(2k+1)2k) \implies f(4k+1) = 1$ due to divisibility. $Q(2k+1,1) \implies f(2(2k+1)\cdot 1)\cdot f(2k(2k+2)) = 1 \implies f(4k+2) = 1$. $Q(2k+2,2k+1) \implies f(4k+3) = 1$. $Q(k+1,2) \implies f(2(k+1) \cdot 2) = 1\implies f(4k+4) = 1$. This completes our induction and we are done.
24.01.2024 06:24
The answer is $f\equiv 1$. Check that this works, and it is easy to show for small $n$. Then, if $n=2k$ is even, \[f(k^2-1)f(2k)=f\left((k^2+1)^2\right)=f(k)^2f(1)^2\]and if $n=2k+1$ is odd, \[f(2k+1)f(2k^2+2k)=f(2k^2+2k+1)^2=f(k)^2f(k+1)^2\]and we are done by induction.
13.03.2024 18:35
first, we can very easily prove $f(1) = 1$, $f(a^2 + 1) = f(a)$, and $f(2a) = f(a)$ we now proceed by recursion if $f(p)=1$, $f(p^2+1)=1$, and $f(2p^2+2)=1$, but $f(2p^2+2)=f(p+1)f(p-1)$, so $f(p+1)=f(p-1)=1$ therefore, we get that all $f(x)=1$, and that is our only solution
13.03.2024 23:58
We claim that the solution is $f \equiv 1$, which works. We will prove that $f(1) = f(2) = \cdots = f(2n) = 1$ for any positive integer $n$ by strong induction on $n$. For our base case of $n = 1$, we have $f(1)^2 = f(1)$, so $f(1) = 1$. We also find that $f(2) = f(1^2 + 1^2) = f(1)f(1) = 1$ as well. For the inductive step, suppose that when $n=k$, all of $f(1), f(2), \ldots, f(2k)$ equal $1$; we then wish to prove that $f(2k + 1) = f(2k + 2) = 1$. We will need the following result: Claim: For $a, b \in \mathbb{N}$, if $f(a) = f(b) = 1$ and $a > b$, then $f(2ab) = 2(a^2 - b^2) = 1$. Proof: Observe that $(a^2 - b^2)^2 + (2ab)^2 = (a^2 + b^2)^2$. Therefore $$f(a^2 - b^2)f(2ab) = f(a^2 - b^2)^2 + (2ab)^2) = f((a^2 + b^2)^2) = f(a^2 + b^2)^2 = (f(a)f(b))^2 = 1,$$which means that $f(a^2 - b^2) = f(2ab) = 1$. Taking $a = k + 1$ and $b = k$, we find that $f(2k + 1) = 1$ as $(k + 1)^2 - k^2 = 2k + 1$. Taking $a = k + 1$ and $b = 1$, we get $f(2k + 2) = 1$. So, we are done.
02.04.2024 00:16
24.04.2024 22:49
First of all, clearly $f(1)=1$ and $f(2)=1$. Since $f(a^2)=f(2a^2)$, we get $f(2a)=f(4a^2)=f(a^2)=f(a)$ [Edit: oops, this part is not correct...]. Also $$f(2a+1)=f((2a+1)^2+1)=f(4a^2+4a+2)=f(2a^2+2a+1)=f(a^2+(a+1)^2)=f(a)f(a+1).$$So by induction it follows that $f(x)\equiv 1$, which is indeed a solution.
26.04.2024 00:44
We show that $f \equiv 1$ by induction. Note that $f(2)=f(1)f(1)=1$ because $0$ is not in the domain. Also note that $f(a)f(b)=1$ means that $f(a)=f(b)=1$ as there are no other numbers in the domain that have a product of $1.$ Thus, splitting cases into evens and odds we have that \begin{align*} f(2K)f(k^2-1)=f(k^2+1)&=f(k)^2f(1)^2=1 \\ f(2k+1)f(2k^2+2k)=f(2k^2+2k+1)^2=f(k)^2f(k+1)^2=1. \end{align*}This completes the induction.$\blacksquare$
15.08.2024 19:32
We claim the answer is $f(x) = 1$ only. We will that $f(n) = 1$ with strong induction on $n$: Base case: Our base cases are $n=1$ and $n=2$. The former follows from plugging $a=1$ into the second given equation, while the latter follows from plugging in $(a,b) = (1,1)$ into the first given equation. Inductive step: For $n$ of the form $2k$ where $k > 1$, we use the identity \[(2k)^2 + \left( k^2 -1 \right)^2 = \left( k^2 + 1 \right)^2\]which lets us go from $f(1) = 1$ and $f(k) = 1$ to $f(2k) = 1$. For $n$ of the form $2k+1$, we use the identity \[(2k+1)^2 + (2k^2 + 2k)^2 = \left( k^2 + (k+1)^2 \right)^2,\]which lets us go from $f(k) = 1$ and $f(k+1) = 1$ to $f(2k+1) = 1$.
22.08.2024 07:53
We claim that the answer is $f(x)=1$ for all $x\in\mathbb{N}$, and this solution clearly satisfies the equation. First, we have $f(1^2)=f(1)^2$, giving $f(1)=1$. We also have $f(2)=f(1^2+1^2)=f(1)^2=1$ Suppose that $a^2+b^2=c^2$ for some $a,b,c\in\mathbb{N}$. Then, we get \[f(c)^2=f(c^2)=f(a^2+b^2)=f(a)f(b).\]Using strong induction, we will prove $f(2n+1)$ and $f(2n+2)$ are both $1$ assuming $f(x)=1$ for $x\in\{1,2,\ldots, 2n\}$. We have \[1=(f(n)f(n+1))^2=f((n^2+(n+1)^2)^2)=f((2n+1)^2+(2n^2+2n)^2)=f(2n+1)f(2n^2+2n),\]giving $f(2n+1)=1$. Similarly, we have \[1=(f(n+1)f(1))^2=f(((n+1)^2+1^2)^2)=f((2n+2)^2+f(n^2+2n)^2) = f(2n+2)f(n^2+2n),\]giving $f(2n+2)$, and this completes our induction, as desired.
09.09.2024 13:57
We will prove that $\boxed{f\equiv1}$. We first use $P(1,1)$ to obtain $f(1)=1$. We then use $P(a,1)$ to obtain that $f(a^2+1)=f(a)$. Now we will show via strong induction that if $f(x)=1$ for $1\leq x \leq n$ then $f(n+1)=1$. Base cases $n=1,2$ can be easily verified. Case 1: If $n+1$ is odd We will write $n+1$ as $2k+1$. We can construct a Pythagorean triplet $\{ a,b,c\}=\{2k+1,2k^2+2k,2k^2+2k+1\}$. From $f(2k+1,2k^2+2k)$ we get $$f((2k+1)^2+(2k^2+2k)^2)=f(2k+1)f(2k^2+2k)$$$$f((2k^2+2k+1)^2)=f(2k+1)f(2k^2+2k)$$$$f(2k^2 + 2k + 1)^2=f(2k+1)f(2k^2+2k)$$$$f(k^2 + (k+1)^2)^2=f(2k+1)f(2k^2+2k)$$$$f(k)f(k+1)f(k)f(k+1)=f(2k+1)f(2k^2+2k)$$$$1=f(2k+1)f(2k^2+2k)$$$$\Rightarrow f(2k+1)=1 \Rightarrow \boxed{f(n+1) = 1}$$Case 2: If $n+1$ is even We will write $n+1$ as $2k$. We can construct a Pythaogrean triplet $\{a,b,c\}=\{k^2-1,2k,k^2+1\}$. From $f(k^2-1,2k)$ we get $$f((k^2-1)^2+(2k)^2)=f(k^2-1)f(2k)$$$$f(k^4+2k^2+1)=f(k^2-1)f(2k)$$$$f((k^2+1)^2)=f(k^2-1)f(2k)$$$$f(k^2+1)^2=f(k^2-1)f(2k)$$$$f(k)^2=f(k^2-1)f(2k)$$$$1=f(k^2-1)f(2k)$$$$\Rightarrow f(2k)=1 \Rightarrow\boxed{f(n+1)=1}$$