12
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ Well, haven't you proved it already? Or am I missing your question? $\endgroup$ May 1, 2022 at 2:27
  • $\begingroup$ He has only considered the polynomial case. $\endgroup$ May 1, 2022 at 2:28
  • 2
    $\begingroup$ @ultralegend5385 No, there are missing other kind of functions. Hence, I must prove that if $f$ holds the condition, it must be a polynomial. $\endgroup$
    – Lord Vader
    May 1, 2022 at 2:38
  • $\begingroup$ Personally, I wonder if this might be a job for a computer program. Making no assumptions about the nature of $f(x)$, and letting $a_k$ denote $f(k)$, I get the following partial results: [1] $1 \leq a_k \leq 7k + 24$ [2] $f(a_k) = f(a_1) + 15(k-1) - 2(a_k - a_1).$ $\endgroup$ May 1, 2022 at 3:07
  • $\begingroup$ As ugly as my previous comment is, it at least has the benefit of recognizing that the only way to attack the problem is by focusing on the fact that the domain of $f(x)$ is the positive integers, and the range of $f(x)$ must be some subset of the positive integers. $\endgroup$ May 1, 2022 at 3:09

3 Answers 3

12
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Why did I use a single step vector recurrence when a two step recurrence will serve better? Well done :-) $\endgroup$ May 1, 2022 at 8:01
  • $\begingroup$ @JyrkiLahtonen Thank you! It's good to have some variability, even though both approaches are isomorphic I guess in the end.. $\endgroup$
    – Sil
    May 1, 2022 at 8:07
4
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .