#6 Functional Equations on Integers

For \(n>0\), induction gives \(f(n)=4n-1\). For \(n<0\), from \(f(n)=f(n+1)-4\) we get the same formula. The answer is \(f(n)=4n-1\).

If \(n=2k\), then \(f(n)=2+6k=3n+2\). If \(n=2k+1\), then \(f(n)=5+6k=3n+2\). The answer is \(f(n)=3n+2\). The formula also works for negative \(k\), since the recurrence is reversible.

Then \(g(m+n)=f(m+n)+1=f(m)+f(n)+2=g(m)+g(n)\). On \(\mathbb N\), \(g(n)=ng(1)=5n\). Hence \(f(n)=5n-1\).

Let \(c=f(0)\). By induction, \(f(1)\equiv c+1\), \(f(2)\equiv c+2\), and so on. Since all values are taken modulo \(7\), we get \(f(x)\equiv c+x\pmod 7\) for every residue \(x\).

The condition is equivalent to \(f(n+2)-f(n+1)=f(n+1)-f(n)\). Thus first differences are constant. Since \(f(1)-f(0)=2\), we have \(f(n+1)-f(n)=2\) for all \(n\). Hence \(f(n)=2n\).

For \(n>0\), \(f(n)=nf(1)=-3n\). Also \(f(0)=0\), and from \(0=f(n+(-n))\), we get \(f(-n)=-f(n)=3n\). Thus for all \(n\in\mathbb Z\), \(f(n)=-3n\).

Let \(g(n)=f(n)-n^2\). Then \(g(m+n)=f(m+n)-(m+n)^2=f(m)+f(n)+2mn-m^2-2mn-n^2=g(m)+g(n)\). Hence \(g(n)=cn\), where \(c\in\mathbb Z\). The answer is \(f(n)=n^2+cn\).

Let \(B(n)=\binom{n}{2}=\frac{n(n-1)}{2}\). Then \(B(m+n)=B(m)+B(n)+mn\). Hence \(g(n)=f(n)-B(n)\) is additive on \(\mathbb Z\), so \(g(n)=cn\). The answer is \(f(n)=\binom{n}{2}+cn\), where \(c\in\mathbb Z\).

Put \(n=1\): \(f(m+1)+f(m-1)=2f(m)\). This means \(f(m+1)-f(m)=f(m)-f(m-1)\), so first differences are constant. Therefore \(f(n)=an+b\). All such functions indeed work.

For every \(n\), the number \(2n+1\) is odd. Hence \(f(n+1)\) and \(f(n)\) have opposite parity. Therefore all values of the function cannot have the same parity. Contradiction.

With \(n=1\), \(f(m+1)+f(m-1)=2f(m)+2\). Hence \(f(m+1)-f(m)=f(m)-f(m-1)+2\). Let \(d_m=f(m)-f(m-1)\). Then \(d_{m+1}=d_m+2\), and \(d_1=f(1)-f(0)=1\). Thus \(d_m=2m-1\) for positive \(m\), and summing gives \(f(n)=1+3+\cdots+(2n-1)=n^2\). For negative \(n\), the equation with \(m=0\) gives \(f(-n)=f(n)\). Therefore \(f(n)=n^2\) for all integers \(n\).

The condition gives \(g(mn)=g(m)+g(n)\). For a prime \(p\), \(g(p)=1\). If \(n=p_1^{a_1}\cdots p_k^{a_k}\), then \(g(n)=a_1+\cdots+a_k\). Hence \(f(n)=n(a_1+\cdots+a_k)\), that is, \(f(n)=n\Omega(n)\), where \(\Omega(n)\) is the number of prime factors counted with multiplicity.

Let \(a=f(1)\). For a residue \(x\), we have \(x=1+\cdots+1\) modulo \(p\). Then \(f(x)=xf(1)=ax\). This also holds for \(x=0\), since \(f(0)=0\).

With \(n=0\), \(f(f(m))=f(0)+m\). If \(f(a)=f(b)\), then \(f(f(a))=f(f(b))\), hence \(a=b\); so \(f\) is injective. With \(m=0\), \(f(n+f(0))=f(n)\), hence \(f(0)=0\). Thus \(f(f(m))=m\). Put \(m=f(t)\): \(f(n+t)=f(n)+f(t)\). Therefore \(f\) is additive on \(\mathbb Z\), so \(f(n)=cn\). From \(f(f(n))=n\), we get \(c^2=1\). The answer is \(f(n)=n\) and \(f(n)=-n\).

For \(g(n)=f(n)+2\), we get \(g(m+n)=g(m)+g(n)\). Thus \(g(n)=an\), where \(a\in\mathbb Z\), and \(f(n)=an-2\). Then \(f(f(n))=a(an-2)-2=a^2n-2a-2\). This equals \(n\) for all \(n\), so \(a^2=1\) and \(-2a-2=0\). Therefore \(a=-1\). The answer is \(f(n)=-n-2\).

By additivity on residues, \(f(x)=ax\), where \(a=f(1)\). Then \(f(f(x))=a^2x\). The condition gives \(a^2\equiv1\pmod p\). Since \(p\) is an odd prime, \((a-1)(a+1)\equiv0\pmod p\), so \(a\equiv1\) or \(a\equiv-1\). The answer is \(f(x)=x\) and \(f(x)=-x\) modulo \(p\).

For \(n>0\), \(f(n)=\sum_{k=0}^{n-1}(2k+1)=n^2\). For negative \(n\), move backwards: \(f(n)=f(n+1)-(2n+1)\), and the same formula \(n^2\) satisfies the recurrence and the initial value. The answer is \(f(n)=n^2\).

Notice that \(4mn=(m+n)^2-(m-n)^2\). Let \(u=m+n\), \(v=m-n\). Then \(u\) and \(v\) have the same parity, and the condition says \(f(u)-u^2=f(v)-v^2\). Hence \(f(n)-n^2\) is constant separately on even and on odd \(n\). Thus all solutions are \(f(n)=n^2+c_0\) for even \(n\) and \(f(n)=n^2+c_1\) for odd \(n\), where \(c_0,c_1\in\mathbb Z\). The check is immediate because \(m+n\) and \(m-n\) always have the same parity.

The function \(n^2\) satisfies the recurrence and the three initial values. A step-three recurrence determines values separately on the classes \(0,1,2\pmod3\). The initial values on these three classes agree with \(n^2\), so by induction forward and backward \(f(n)=n^2\) for all integers \(n\).

With \(x=0\), \(f(f(y))=f(0)+y\). If \(f(a)=f(b)\), then \(f(f(a))=f(f(b))\), hence \(a=b\); the function is injective. On a finite set it is bijective. With \(y=0\), \(f(x+f(0))=f(x)\), so \(f(0)=0\). Thus \(f(f(y))=y\).

Put \(y=f(t)\): \(f(x+t)=f(x)+f(t)\). Hence \(f\) is additive on \(\mathbb Z/p\mathbb Z\), so \(f(x)=ax\). From \(f(f(x))=x\), we get \(a^2\equiv1\pmod p\). Since \(p\) is an odd prime, \(a\equiv1\) or \(a\equiv-1\). The answer is \(f(x)=x\) and \(f(x)=-x\) modulo \(p\).