2003 USA TST #4

Let $\mathbb{N}$ denote the set of positive integers. Find all functions $f: \mathbb{N} \to \mathbb{N}$ such that\[ f(m+n)f(m-n) = f(m^2)  \]for $m,n \in \mathbb{N}$.

The answer is $\boxed{f \equiv 1}$.

Let $f(1)=a, f(2)=b, f(3)=c$. 

$$f\left(4\right)=f\left(2^2\right)=f\left(2-1\right)f\left(2+1\right)=f\left(1\right)f\left(3\right)=ac$$

$$af\left(5\right)=f\left(1\right)f\left(5\right)=f\left(3-2\right)f\left(3+2\right)$$ $$=f\left(3^2\right)$ $=f\left(3-1\right)f\left(3+1\right)=f\left(2\right)f\left(4\right)=b\cdot ac$$

This $af(5)=b \cdot ac$ implies $f(5)=bc$. 

$$bf\left(6\right)=f\left(2\right)f\left(6\right)=f\left(4-2\right)f\left(4+2\right)$$ $$=f\left(4^2\right)$ $=f\left(4-1\right)f\left(4+1\right)=f\left(3\right)f\left(5\right)=c\cdot bc=bc^2$$

This $bf(6)=bc^2$ implies $f(6)=c^2$. 

$$cf\left(7\right)=f\left(3\right)f\left(7\right)=f\left(5-2\right)f\left(5+2\right)$$ $$=f\left(5^2\right)$ $=f\left(5-1\right)f\left(5+1\right)=f\left(4\right)f\left(6\right)=ac\cdot c^2=ac^3$$

This $cf(7)=ac^3$ implies $f(7)=ac^2$. 

$$a^2c^2=a\cdot ac^2=f\left(1\right)f\left(7\right)=f\left(4-3\right)f\left(4+3\right)$$ $$=f\left(4^2\right)$ $=f\left(4-1\right)f\left(4+1\right)=f\left(3\right)f\left(5\right)=c\cdot bc=bc^2$$

This $a^2c^2=bc^2$ implies $a^2=b$. So, $f(2)=b=a^2$ and $f(5)=bc=a^2c$. 

$$ac\cdot f\left(8\right)=f\left(4\right)f\left(8\right)=f\left(6-2\right)f\left(6+2\right)$$ $$=f\left(6^2\right)$ $=f\left(6-1\right)f\left(6+1\right)=f\left(5\right)f\left(7\right)=a^2c\cdot ac^2=a^3c^3$$

This $ac \cdot f(8)=a^c^3$ implies $f(8)=a^2c^2$. 

$$a^4c^2=a^2\cdot a^2c^2=f\left(2\right)f\left(8\right)=f\left(5-3\right)f\left(5+3\right)$$ $$=f\left(5^2\right) =f\left(5-1\right)f\left(5+1\right)=f\left(4\right)f\left(6\right)=ac\cdot c^2=ac^3$$.

This $a^4c^2=ac^3$ implies $a^3=c$. 

We use all of our results up till now to get 

$f\left(1\right)=a$;$f\left(2\right)=a^2$;$f\left(3\right)=c=a^3$;$f\left(4\right)=ac=aa^3=a^4$;$f\left(5\right)=a^2c=a^2a^3=a^5$;$f\left(6\right)=c^2=\left(a^3\right)^2=a^6$;$f\left(7\right)=ac^2=a\left(a^3\right)^2=a^7$;$f\left(8\right)=a^2c^2=a^2\left(a^3\right)^2=a^8$.

Then, $$af\left(9\right)=f\left(1\right)f\left(9\right)=f\left(5-4\right)f\left(5+4\right)=f\left(5^2\right)$$ $$=f\left(5-1\right)f\left(5+1\right)=f\left(4\right)f\left(6\right)=a^4\cdot a^6=a^{10}$$

which gives $f(9)=a^9$. It follows that $$a^9=f\left(9\right)=f\left(3^2\right)=f\left(3-1\right)f\left(3+1\right)=f\left(2\right)f\left(4\right)=a^2a^4=a^6$$

so $a=1$. 

At this point, we will use induction to show the desired. For $n=1,2,3,4,5$, note that $f(x)=1$ easily follows from $f(1)=a, f(2)=a^2, f(3)=a^3, f(4)=a^4, f(5)=a^5$ along with $a=1$. Now assume that $x \ge 5$ and $f(x)=1$ for all positive integers less than $x$. In particular, we would have $f(x-1)=1, f(x-3)=1, f(x-4)=1$. Then, note that 

$$f\left(N\right)=1\cdot f\left(N\right)=f\left(N-4\right)f\left(N\right)=f\left(\left(N-2\right)-2\right)f\left(\left(N-2\right)+2\right)$$ $$=f\left(\left(N-2\right)^2\right)=f\left(\left(N-2\right)-1\right)f\left(\left(N-2\right)+1\right)=f\left(N-3\right)f\left(N-1\right)$$ $$=1\cdot 1,$$ 

so this completes the induction. 

We are done. $\square$