Find all the functions $f:\mathbb{Z}^+ \to \mathbb{Z}^+$ such that $f(f(x)) = 15x-2f(x)+48$.

Question

Find all the functions $f:\mathbb{Z}^+ \to \mathbb{Z}^+$ such that $f(f(x)) = 15x-2f(x)+48$.

If $f$ is a polynomial of degree $n$, we have that $\deg(f(f(x))) = n^2$ and $\deg(15x-2f(x)+48)=n$. Therefore, the only possible polynomials that satisfy the condition have degree $0$ or $1$.

Let $f:\mathbb{Z}^+ \to \mathbb{Z}^+$ be a function that holds the condition of the problem given by $f(x)=ax+b$ for some constants $a$ and $b$. Since $$f(f(x)) = f(ax+b) = a(ax+b)+b = a^2x + (a+1)b$$ and $$15x-2f(x)+48 = 15x-2(ax+b)+48 = (15-2a)x+(48-2b),$$ it follows that $$a^2+2a-15=0 \quad\text{and}\quad (a+1)b=48-2b.$$ From the first equation, we get that $a=-5$ or $a=3$. If $a=-5$, from the second equation we get that $b=-24$, and it contradicts that $f[\mathbb{Z}^+]\subseteq \mathbb{Z}^+$. If $a=3$, then $b=8$. Therefore, $f(x)=3x+8$ is the only polynomial that satisfies the condition of the problem. I guess that this is the only solution, but I do not know how to prove it.

Edit: I was trying to prove that the iterations of any function $f$ that satisfies the problem have the same behaviour. For instance, by iterating $f$ we have that $2f^3(x)+f^4(x)-15f^2(x)=48$, so this functions are almost the same except for constant terms. Is this usefull this idea to complete the problem?

Answer 1

Note: the proof of convergence of the sequence used below is not complete, I might come back later to fix it, but there are already other answers anyway.

---

Due to the requirement that $f(x) \in \mathbb{Z}^+$ whenever $x \in \mathbb{Z}^+$, we must have $15x - 2f(x) + 48 \gt 0$, so

$$f(x) \lt \frac{15x + 48}{2}\tag{1}$$

By substituting $x$ with $f(x)$ in $(1)$, we obtain

$$f(f(x)) \lt \frac{15 f(x) + 48}{2}\tag{2}$$

Using the functional equation to eliminate $f(f(x))$ we get $$15x - 2f(x) + 48 \lt \frac{15f(x) + 48}{2}\tag{3}$$

Combining (1) and (3), it follows that $$f(x) \gt \frac{30x + 48}{19}\tag{4}$$

Substituting $x$ with $f(x)$ in (4) and using the functional equation we get $$15x - 2f(x) + 48 \gt \frac{30f(x) + 48}{19}\tag{5}$$

From this it follows that $$f(x) \lt \frac{285x + 864}{68}\tag{6}$$

---

We can keep continuing the same way. In order to discover a pattern while repeating this, suppose we have found so far that $$ax + b \lt f(x) \lt Ax + B\tag{7}$$ for some coefficients $a, b, A, B$. Then by substituting $x$ with $f(x)$ and applying the functional equation, we get $$af(x) + b \lt 15x - 2f(x) + 48 \lt Af(x) + B$$ and therefore $$\frac{15}{A + 2}x + \frac{48 - B}{A + 2} \lt f(x) \lt \frac{15}{a + 2}x + \frac{48 - b}{a + 2} \tag{8}$$

From (7) and (8) we obtain a sequence of coefficients $a_n, b_n, A_n, B_n$ satisfying the recurrence

$$\begin{pmatrix}a_{n+1} \\ b_{n+1} \\ A_{n+1} \\ B_{n+1}\end{pmatrix} = \begin{pmatrix}\frac{15}{A_n + 2} \\ \frac{48 - B_n}{A_n + 2} \\ \frac{15}{a_n + 2} \\ \frac{48 - b_n}{a_n + 2}\end{pmatrix} = \mathbf{F}\begin{pmatrix}a_n \\ b_n \\ A_n \\ B_n\end{pmatrix}\tag{9}$$

Now assuming the sequence (9) converges, it must converge to a fixed point of $\mathbf{F}$. The fixed points are found by solving the equations $$\begin{pmatrix}a \\ b \\ A \\ B\end{pmatrix} = \begin{pmatrix}\frac{15}{A + 2} \\ \frac{48 - B}{A + 2} \\ \frac{15}{a + 2} \\ \frac{48 - b}{a + 2}\end{pmatrix}$$

From the first and third components we get a quadratic with two solutions. But only one is positive and since we started with $a_0 = 0, b_0 = 0, A_0 = \frac{15}{2}, B_0 = \frac{48}{2} = 24$, it will be the one to use. This solution is $a = A = 3$. Then we can solve for $b$ and $B$ from the second and fourth equations to obtain $b = B = 8$.

This means that by repeating the procedure described above, we can get a sequence of inequalities

$$a_nx + b_n \lt f(x) \lt A_nx + B_n$$

where $a_n, A_n$ are arbitrarily close to $3$ and $b_n, B_n$ are arbitrarily close to $8$, so that $f(x)$ is arbitrarily close to $3x + 8$ (pointwise). For any fixed integer $x$, we can repeat this procedure finitely many times before the error in approximation is less than $1/2$ and by the requirement that $f(x)$ is an integer, it must be equal to $3x + 8$.

---

Proof of convergence of the sequence (9)

The initial conditions are $a_0 = 0, b_0 = 0, A_0 = \frac{15}{2}, B_0 = \frac{48}{2} = 24$.

Looking at the first and third components, we have the coupled recurrence equations $$a_{n+1} = \frac{15}{A_n + 2}$$ $$A_{n+1} = \frac{15}{a_n + 2}$$

It can be checked that $0 \leq \frac{15}{x + 2} \lt 3$ when $x \gt 3$ and $\frac{15}{x + 2} \gt 3$ when $0 \leq x \lt 3$. Using this fact and induction it is clear that $0 \leq a_n \lt 3 \lt A_n$ for all $n$.

We can decouple the equations to obtain the recurrence $$x_{n+2} = \frac{15x_n + 30}{2x_n + 19}$$ where $x_n$ can be either $a_n$ or $A_n$.

The function $\frac{15x + 30}{2x + 19}$ is strictly increasing when $x \geq 0$. It can also be checked that $\frac{15x + 30}{2x + 19} \gt x$ when $0 \leq x \lt 3$ and $\frac{15x + 30}{2x + 19} \lt x$ when $x \gt 3$.

This means that if $0 \leq x_n \lt 3$ then $x_n \lt x_{n+2} \lt 3$ and if $x_n \gt 3$ then $x_n \gt x_{n+2} \gt 3$.

Since $a_0 = 0$ and $A_0 = \frac{15}{2}$, this result shows that $$0 \leq a_n \lt a_{n+2} \lt 3 \lt A_{n+2} \lt A_n\text{ for all }n$$

This shows that the subsequences $a_{2n}, a_{2n+1}$, $A_{2n}$, $A_{2n+1}$ are all bounded and monotonic, so they each converge. From the recurrence we get $A_1 = \frac{15}{a_0 + 2} = \frac{15}{2} = A_0$ and $a_2 = \frac{15}{A_1 + 2} = \frac{15}{A_0 + 2} = a_1$. This means that the subsequences $a_{2n+1}$ and $a_{2n+2}$ are identical, and similarly $A_{2n}$ and $A_{2n+1}$ are identical, so in fact the sequences $a_n$ and $A_n$ converge to positive values $a$ and $A$. Since $a$ and $A$ must be fixed points of the recurrence, the only possibility is $a = 3 = A$.

Now we look at the second and fourth components of (9): $$b_{n+1} = \frac{48 - B_n}{A_n + 2}$$ $$B_{n+1} = \frac{48 - b_n}{a_n + 2}$$

This can be written in matrix form as $$\begin{pmatrix}b_{n+1} \\ B_{n+1}\end{pmatrix} = \begin{pmatrix}0 & -\frac{1}{A_n + 2} \\ -\frac{1}{a_n + 2} & 0\end{pmatrix}\begin{pmatrix}b_n \\ B_n\end{pmatrix} + \begin{pmatrix}\frac{48}{A_n + 2} \\ \frac{48}{a_n + 2}\end{pmatrix}$$ or more compactly as $$\mathbf{b}_{n+1} = \mathbf{A}_n\mathbf{b}_n + \mathbf{u}_n$$ where $\mathbf{b}_n = \begin{pmatrix}b_n \\ B_n\end{pmatrix}$, $\mathbf{A}_n = \begin{pmatrix}0 & -\frac{1}{A_n + 2} \\ -\frac{1}{a_n + 2} & 0\end{pmatrix}$ and $\mathbf{u}_n = \begin{pmatrix}\frac{48}{A_n + 2} \\ \frac{48}{a_n + 2}\end{pmatrix}$.

The general solution is $$\mathbf{b}_n = \left(\mathbf{A}_{n-1}\cdots\mathbf{A}_0\right)\mathbf{b}_0 + \sum\limits_{i = 0}^{n-1}\left(\mathbf{A}_{n-1}\cdots\mathbf{A}_{i+1}\right)\mathbf{u}_i$$

Convergence should follow from the fact that the $\mathbf{A}_n$ have Frobenius norm less than $1$ and the $\mathbf{u}_n$ are bounded.

Answer 2

Let us study the two variable affine transformation $g:\Bbb{R}^2\to\Bbb{R}^2$ $$ g(x,y)=(y,15x-2y+48). $$ The connection to the problem is, of course, that $g(x,f(x))=(f(x),f(f(x)))$. I am using the idea from Tob's answer that unless we are on the straight and narrow path of $f(x)=3x+8$ we will diverge to a point where negative values will appear.

The linear part of the transformation $g$ comes from the matrix $$ A=\left(\begin{array}{rr}0&1\\ 15&-2\end{array}\right). $$ Suggestively, the eigenvalues of $A$ are $\lambda_1=3$ with eigenvector $(1,3)^T$ and $\lambda_2=-5$ with eigenvector $(1,-5)^T$. The idea is that if we iterate $g$ from a starting point that has a non-zero component belonging to that large negative eigenvalue, then eventually $(-5)^m$ dominates over $3^m$, kicking us out of the positive zone.

Let's first linearize. We easily find that $P=(-4,-4)$ is a fixed point of $g$ (as $P$ is on the expected line $y=3x+8$ this, again, boosts our optimism). So if we move the origin to $P$ we need to write $u=x+4, v=y+4$, and replace $g(x,y)$ with $$h(u,v)=(v,15u-2v).$$ The connection to the functional equation now reads: $$ h(x+4,f(x)+4)=(f(x)+4,f(f(x))+4). $$

We can now prove that we run into a contradiction, if $f(a)=b\neq 3a+8$ for some integer $a>0$. We write $(a+4,b+4)$ using the eigenbasis above $$ (a+4,b+4)=c_1(1,3)+c_2(1,-5). $$ The contrapositive assumption is equivalent to $c_2\neq0$.

When we iterate $m$ times we arrive at $$ (a_m+4,b_m+4)=3^mc_1(1,3)+(-5)^mc_2(1,-5), $$ where, $a_0=a$, $b_0=b$ and for all $m>0$, $b_m=f(a_m)$ and $a_{m+1}=b_m$.

It is then clear that the assumption $c_2\neq0$ forces $b_m<0$ for some large enough value of $m$, which is a contradiction.

Answer 3

Put $a_0=a \in \mathbb{Z}^{+}$ arbitrary and $a_n=f(a_{n-1})$ for $n \geq 1$. The functional equation gives a non-homogenous linear recurrence $$ a_{n}=-2a_{n-1}+15a_{n-2}+48. $$ Homogenizing it by substitution $b_n=a_n+4$ we get $$ b_n=-2b_{n-1}+15b_{n-2}. $$ The characteristic equation is $x^2+2x-15=(x+5)(x-3)$, hence by the standard result for linear recurrences we have some constants $A,B$ such that $$ a_n=A3^n+B(-5)^n-4. $$ If $B\neq 0$, the term $(-5)^n$ will dominate over $3^n$ in $a_n$ for sufficiently large $n$, regardless of value of $A$. Hence $a_n$ will be arbitrary large negative or positive value, based on the parity of $n$. However, we know $a_n=f(a_{n-1})$ must be positive for $n \geq 1$, thus $B=0$. Also from $n=0$ we find $A=a+4$, and overall $$ a_n=3^n(a+4)-4. $$ Finally, from $n=1$ we obtain $f(a)=a_1=3(a+4)-4=3a+8$. Since $a$ was arbitrarily chosen, we have $f(x)\equiv 3x+8$. Plugging back to the functional equation verifies it is indeed a solution and by the above construction also the only one.