Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ such that for all integers $n \in \mathbb{N}$, $2f(f(n)) = 5f(n) - 2n$.

Question

I proved solution is $f(x) = 2x$ by considering case where $c$ does not equal $0$ in the function $f(x)=kx+c$. By direct substitution, i.e., algebra, I showed that $c$ must be zero and $k=2$. I am pretty confident about that. But did I need to show that it must be a linear equation? Or is that trivial?

Answer 1

Let $f$ be such a function.

Let $k \in \mathbb{N}$. Let $(u_n)_{n \in \mathbb{N}}$ be the sequence of integers defined by $$u_0=k \quad \text{and} \quad \forall n \geq 0,\ u_{n+1}=f(u_n)$$

For every $n \in \mathbb{N}$, the assumption on $f$, applied to $u_n$, gives $$2f(f(u_n))=5f(u_n)-2u_n, \quad \text{i.e.} \quad 2u_{n+2}-5u_{n+1}+2u_n =0$$

Solving this recursion, we get that there exists two constant $\alpha, \beta \in \mathbb{R}$ such that $$\forall n \in \mathbb{N}, \quad u_n = \alpha 2^n + \beta \dfrac{1}{2^n}$$

Since $u_0=k$, one gets that $\alpha + \beta = k$, so $$u_n = 2^nk +\beta \left(\dfrac{1}{2^n}-2^n\right)$$

But this must be an integer for every $n$ : in particular, for every $n \in \mathbb{N}$, one must have $$\beta \left(\dfrac{1}{2^n}-2^n\right) \in \mathbb{Z}, \quad \text{i.e. there exists $\gamma_n \in \mathbb{Z}$ such that } \beta = \dfrac{2^n}{1-4^n}\gamma_n$$

So for every $n \in \mathbb{N}$, one has $$ \dfrac{2^{n+1}}{1-4^{n+1}}\gamma_{n+1} = \dfrac{2^n}{1-4^n}\gamma_n, \quad \text{i.e.} \quad \gamma_{n+1} = \dfrac{1-4^{n+1}}{2(1-4^n)}\gamma_n$$

so $$\gamma_n = \left(\prod_{k=1}^{n-1} \dfrac{1-4^{k+1}}{2(1-4^k)}\right) \gamma_1= \dfrac{1}{2^{n-1}} \dfrac{4^{n}-1}{3} \gamma_1 $$

In particular, $2^{n-1}$ must divide $(4^n-1)\gamma_1$, so it must divide $\gamma_1$ for every $n \in \mathbb{N}$. So $\gamma_1=0$, so $\beta=0$.

Finally, one has $$\forall n \in \mathbb{N}, \quad u_n = \alpha 2^n$$

and since $u_0=k$ and $u_1=f(k)$, one gets $$f(k)=2k$$

This being true for every $k \in \mathbb{N}$, one has finally that the only possible function $f$ is $$\boxed{f : k \mapsto 2k}$$

Answer 2

(Essentially the same as TheSilverDoe's but much simplified.)

For questions like this, the key crux is to fix an $n$ and define $f^{(k)} (n) = f_k $, set up the recurrence relation, solve it and draw conclusions from there.

1. Set up the recurrence relation
   $ 2f_{k+2} = 5f_{k+1} - 2f_k$.
2. Solve the recurrence relation
   $2x^2 - 5x + 2 = (2x-1)(x-2)$ so $ f_k = \alpha 2^k + \beta 2^{-k} $.
3. Would love to conclude that $ \beta = 0 $
   $f_{k+1} - 2f_k = \beta 2^{-k-1} - 2 \beta 2^{-k} = \beta \times (-3) 2^{-k-1} $ is an integer for all $k$, so clearly $ \beta = 0 $.
4. Thus $f(n) = 2n$ is the only possible value.
   We do still have to verify that it actually works, which it does.

---

For a similar question, solve $f: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+, f(f(n)) + f(n) = 6n$.
How would you modify step 3 to make use of the positivity condition?