Find all functions $f:\mathbb{Z}\rightarrow\mathbb{C}$ such that $f(x(2y+1))=f(x(y+1))+f(x)f(y)$ holds for any two integers $x,y$.
Problem
Source: Israel National Olympiad 2016 Q7
Tags: algebra, functional equation, function
BlazingMuddy
08.08.2019 06:06
Either $f\equiv 0$ or $f(x) = g(s(x))h(x)$ where $g : \{-1, 1\} \rightarrow \{-1, 1\}$ is a function such that $g(1) = 1$, and $s, h : \mathbb{Z} \rightarrow \mathbb{C}$ are functions such that:
$$ s(x) = \begin{cases}
s(x) = 1, x \geq 0 \\
s(x) = -1, x < 0 \end{cases} $$and $h$ is one of the following:
1. $h(x) = x \; \forall x \in \mathbb{Z}$
2. $h(x) = 1$ if $x$ is odd and $h(x) = 0$ is $x$ is even
3. $h(x) = 1$ if $3 | x - 1$, $h(x) = -1$ if $3 | x + 1$, and $h(x) = 0$ if $3 | x$
Plugging in $x = y = 0$ directly gives us $f(0) = 0$. Next, plugging in $y = -1$ gives us $f(-x) = f(x)f(-1)$ for all $x\in \mathbb{Z}$. In particular, $f(-1) = f(1)f(-1)$, so either $f(-1) = 0$ or $f(1) = 1$. The former gives us $\boxed{f\equiv 0}$. So, now we assume $f\not\equiv 0$, which gives us $f(1) = 1$. Substituting in $x = -1$ in the equation we have just obtained gives us $f(-1)^2 = f(1) = 1$, so either $f(-1) = -1$ or $f(-1) = 1$. The former means $f$ is odd, and the latter means $f$ is even. Either way, we only need to care for the values of $f(x)$ when $x \geq 0$ now, and changing $y$ to $-y$ in both cases gives:
\begin{align*}
f(x(1-2y)) &= f(x(1-y)) + f(x)f(-y) \\
f(x(2y-1)) &= f(x(y-1)) + f(x)f(y) \\
f(xy) + f(x)f(y-1) &= f(x(y-1)) + f(x)f(y) \\
f(xy) - f(x)f(y) &= f(x(y-1)) - f(x)f(y-1)
\end{align*}
For $x, y\geq 0$, by induction on $y$ we can see that
\begin{align*}
f(xy) - f(x)f(y)
&= f(x(y-1)) - f(x)f(y-1) \\
&= f(x(y-2)) - f(x)f(y-2) \\
&= \ldots \\
&= f(0) - f(x)f(0) \\
&= 0
\end{align*}
So, $f$ is completely multiplicative. Now, we simply need to deal with the equation
$$ f(2y+1) = f(y+1) + f(y) \; \forall y\in \mathbb{Z} \ldots(1) $$
Let $f(2) = b$. $(1)$ gives:
\begin{align*}
f(3) &= f(2) + f(1) \\
&= b + 1 \\
f(5) &= f(3) + f(2) \\
&= 2b + 1 \\
f(7) &= f(4) + f(3) \\
&= b^2 + b + 1 \\
f(15) &= f(8) + f(7) \\
f(3)f(5) &= f(2)^3 + f(7) \\
(b+1)(2b + 1) &= b^3 + b^2 + b + 1 \\
&= (b+1)(b^2 + 1) \\
b(b+1)(b-2) &= 0
\end{align*}
So, either $b = -1$, $b = 0$, or $b = 2$.
If $b = -1$, then $f(2) = -1$, $f(3) = 0$, $f(4) = 1$, and by small induction we can see that for all $x\geq 0$,
$$ f(x) = \begin{cases}
1, & 3 | x - 1 \\
-1, & 3 | x + 1 \\
0, & 3 | x
\end{cases} $$
Meanwhile, if $b = 0$, then $f(2) = 0$, leading to $f(x) = 0$ whenever $x$ is even and by small induction again (or whatever) $f(x) = 1$ if $x\geq 0$ is odd.
Finally, if $b = 2$, then $f(2) = 2$, $f(3) = 3$, and again by small induction we can see that $f(x) = x$ for all $x \geq 0$.
Combined with the fact that $f$ is either odd or even, we get all the whopping $7$ possible functions. To check that all functions satisfy the original equation, simply note that all of them are indeed multiplicative and satisfy $f(2y+1) = f(y+1) + f(y)$ for all $y\in \mathbb{Z}$. This is sufficient because then
\begin{align*}
f(x(2y+1)) &= f(x)f(2y+1) \\
&= f(x)(f(y+1) + f(y)) \\
&= f(x)f(y+1) + f(x)f(y) \\
&= f(x(y+1)) + f(x)f(y)
\end{align*}