Find all functions $f:\mathbb{N}\rightarrow \mathbb{N}$ such that for all $m,n\in\mathbb{N}$, \[(2^m+1)f(n)f(2^mn)=2^mf(n)^2+f(2^mn)^2+(2^m-1)^2n. \]
Problem
Source:
Tags: function, quadratics, algorithm, induction, floor function, algebra proposed, algebra
modularmarc101
21.11.2010 23:26
Let $n=1$ and let $a = f(1)$, then
$(2^m + 1)f(2^m)a = 2^m a^2 + f(2^m)^2 + (2^m-1)^2$
$\implies f(2^m)^2 - (2^m+1)a f(2^m) + [2^ma^2 + (2^m-1)^2] = 0$
$\implies f(2^m) = \frac{(2^m+1)a \pm \sqrt{ (2^m+1)^2a^2 - 4(2^ma^2 + (2^m-1)^2) }}{2}$
$\implies f(2^m) = \frac{(2^m+1)a \pm (2^m - 1)\sqrt{ a^2 - 4}}{2}$
Now, $a^2 - 4$ must be a perfect square, which implies that $f(1) = a = 2$, but more importantly, that $\boxed{f(2^m) = 2^m + 1, \ \forall m \in \mathbb{N}_0}$.
spanferkel
23.11.2010 01:10
WakeUp wrote:
Find all functions $f:\mathbb{N}\rightarrow \mathbb{N}$ such that for all $m,n\in\mathbb{N}$,
\[(2^m+1)f(n)f(2^mn)=2^mf(n)^2+f(2^mn)^2+(2^m-1)^2n. \]
The F.E. is equivalently $[2^mf(n)-f(2^mn)][f(2^mn)-f(n)]=(2^m-1)^2n$.
Putting $m=1$ and $n=p$ a prime, we have $[2f(p)-f(2p)][f(2p)-f(p)]=p$, so $\boxed{f(p)=p+1}$, as $f(p)$ is the sum of two integer factors of $p$. And so $f(2p)$ is either $p+2$ or $2p+1$.
Similarly, we have either $f(p^2)=2p$ or $f(p^2)=p^2+1$.
I'm too tired to finish it right now, but I would guess that only the solution $f(n)=n+1$ survives.
math154
23.11.2010 04:46
Let $P(m,n)$ denote the assertion that $(2^m+1)f(n)f(2^mn)=2^mf(n)^2+f(2^mn)^2+(2^m-1)^2n$. First, \[P(1,n)\implies3f(n)f(2n)=2f(n)^2+f(2n)^2+n.\]Treating this as a quadratic in $f(2n)$, we find that $f(n)^2-4n$ is a perfect square for all $n$. Next, \[P(1,2n)\implies3f(2n)f(4n)=2f(2n)^2+f(4n)^2+2n.\]Subtracting the second equation from twice the first, we find that for all $n$, either $f(4n)=2f(n)$ or $f(4n)=3f(2n)-2f(n)$. Now \[P(2,n)\implies5f(n)f(4n)=4f(n)^2+f(4n)^2+9n.\] Assume for the sake of contradiction that some positive integer $t$ exists such that $f(4t)=2f(t)$, and take $t$ to be minimal. Then $P(2,t)\implies2f(t)^2=9t$, so $t=2k^2$ and $f(2k^2)=3k\implies f(8k^2)=6k$ for some positive integer $k$. Thus $f(4k^2)\ne2f(k^2)$ and $f(16k^2)\ne2f(4k^2)$, so $f(4k^2)=3f(2k^2)-2f(k^2)$ and $f(16k^2)=3f(8k^2)-2f(4k^2)$, whence $f(16k^2)=4f(k^2)$ and \[P(4,k^2)\implies17f(k^2)f(16k^2)=16f(k^2)^2+f(16k^2)^2+225k^2\implies f(k^2)=\frac{5k}{2}.\]But this means that $2|k$, so by the minimality of $t$, \[f(2k^2)=3f(k^2)-2f\left(\frac{k^2}{2}\right)\implies f\left(\frac{k^2}{2}\right)=\frac{9k}{4},\]whence $4|k$. Continuing, in this manner, we find that \[f\left(\frac{k^2}{2^j}\right)=\frac{2^{j+2}+1}{2^{j+1}}k,\]contradicting the fact that $k$ is nonzero (note that each time in this algorithm, we get an increase in $v_2(k)$, so it's possible to continue like this). Therefore we have $f(4n)=3f(2n)-2f(n)$ for all $n$. By a simple induction, $f(2^jn)=(2^j-1)f(2n)-(2^j-2)f(n)$. Thus using spanferkel's factorization, \[P(m,n)\Longleftrightarrow[2f(n)-f(2n)][f(2n)-f(n)]=n.\]Clearly, then ($f(4n)-2f(2n)=f(2n)-2f(n)$ and $f(4n)-f(2n)=2[f(2n)-f(n)]$), $f$ is uniquely determined by values of $f(2r+1),f(4r+2)$ for each odd positive integer $2r+1$, with \[f(4r+2)=\frac{3f(2r+1)\pm\sqrt{f(2r+1)^2-4(2r+1)}}{2}>f(2r+1)\]and $f(2r+1)^2-4(2r+1)$ a perfect square.
spanferkel
23.11.2010 19:29
math154 wrote: Continuing, in this manner, we find that \[f\left(\frac{k^2}{2^j}\right)=\frac{2^{j+2}+1}{2^{j+1}}k,\]contradicting the fact that $k$ is nonzero (note that each time in this algorithm, we get an increase in $v_2(k)$, so it's possible to continue like this). Great reasoning! So to wrap it all up, we have modularmarc101 wrote: $\boxed{f(2^m) = 2^m + 1, \ \forall m \in \mathbb{N}_0}$. spanferkel wrote: $\boxed{f(p)=p+1}$ for each prime $p$. math154 wrote: Clearly, $f(4n)-f(2n)=2[f(2n)-f(n)]$), so $f$ is uniquely determined by values of $f(2r+1),f(4r+2)$ for each odd positive integer $2r+1$, with \[f(4r+2)=\frac{3f(2r+1)\pm\sqrt{f(2r+1)^2-4(2r+1)}}{2}>f(2r+1)\]and $f(2r+1)^2-4(2r+1)$ a perfect square. By the factorization $ [2f(n)-f(2n)][f(2n)-f(n)]=n $, the possible values for $f(n)$ are limited to $a+b$, where $n=ab$ ($a,b\in\mathbb N$), and we then get $f(2n)=2a+b$ or $a+2b$. Note that the above discriminant is $(a-b)^2$, thus always a perfect square. So for each odd $n$ which is not a prime, we have more than 1 choice for $f(n)$, in fact exactly $\left\lfloor \frac{\tau(n)}2\right\rfloor$ choices, where $\tau(n)$ is the number of divisors of $n$. This entails 2 choices (or 1 if $a=b$) for $f(2n)$. Together with the above formulas $ \boxed{f(2^{j}n)=(2^{j}-1)f(2n)-(2^{j}-2)f(n) }$, $\boxed{f(p)=p+1}$ and $\boxed{f(2^m) = 2^m + 1}$, these choices determine $f(k)$ for all $k\in\mathbb N$.