Find all function satisfying $f(f(n))+f(n)=2n+3k$

Question

Find all functions $f:\mathbb{N_{0}} \rightarrow \mathbb{N_{0}}$ satisfying the equation $f(f(n))+f(n)=2n+3k,$ for all & $n\in \mathbb{N_{0}}$, where $k$ is a fixed natural number.

A friend of mine suggested me to use recurrence relation. While it is unfortunate that I have problems understanding recurrence relation. Please refer information to understand difference equation, homogeneous equation & auxillary equation.

Thanks in advance! Kindly don't down vote for not showing my attempt. I am seriously not able to understand the question and the process suggested to use.

Answer 1

We will instead, because it is slightly easier, solve the functional equation for functions $f$ which map $\mathbb{N}_0$ to $\mathbb{Z}$, and then pick out the solutions which we find that happen to satisfy the requirement that $f(n) \geq 0$ for all $n$.

Consider some fixed value of $n\in\mathbb{N}_0$, and look at the sequence given by $$ \begin{align*} a_0 & = n \\ a_{m} & = f(a_{m-1}) \text { for } m \geq 1 \end{align*} $$

i.e., We consider the sequence $n, f(n), f(f(n)), f(f(f(n))) \ldots$

From the functional equation, we see that this sequence satisfies the recurrence relation $$ a_{m+2} + a_{m+1} = 2a_m + 3k$$ for all $m \geq 0$. A particular solution to this recurrence relation is given by $$ a_m = n + mk $$ for all $m \geq 0$. The general solution is then given by $$ a_m = b_m + n + mk $$ where $b_m$ is some solution to the homogeneous recurrence relation $$ b_{m+2} + b_{m+1} - 2b_m = 0 $$ for all $m \geq 0$, and $b_0 = 0$.

The characteristic polynomial is $\lambda^2 + \lambda - 2$, which has roots $\lambda = 1$ and $\lambda = -2$. Thus the general solution to this recurrence relation is given by $$ b_m = A(n) 1^m + B(n) (-2)^m $$ where $A$ and $B$ are "constants" which can depend on $n$ (but do not depend on $m$).

Now we know that $a_m \geq 0$ for all $m$, and so we must have that $b_m \geq -n - mk$ for all $m$.

Suppose that $B(n) \neq 0$. For $m$ large enough, we know that $$ |B(n)| 2^m > A(n) + n + mk $$ since the right hand side grows linearly while the left hand side grown exponentially. Consider such a $m$ where $m$ is odd if $B(n)$ is positive, and even if $B(n)$ is negative. Then $$ b_m = A(n) + B(n) (-2)^m = A(n) - |B(n)|2^m < -n-mk $$ which is a contradiction, since we require $b_m \geq -n - mk$ for all $m$.

Thus we must have that $B(n)=0$. The general solution to the recurrence is then $$ b_m = A(n) $$ i.e. The sequence $(b)$ is constant. But we have that $b_0 = 0$, and so $b_m = 0$ for all $m$. Thus the most general solution for the sequence $(a)$ which satisfies $a_m \geq 0$ for all $m$ is given by $$ a_m = n + mk $$

In particular, we find that $$ f(n) = a_1 = n+k $$

This holds for all $n$, and so we see that the only solution to the functional equation (which only takes values in the non-negative integers) is given by $$ f(n) = n+k $$ for all $n$.

Answer 2

The simplest possible answer is:

If $f(n) = an + b$, then

$f(f(n)) = a(an+b)+b = a^2n+ba+b$

and

$f(f(n)) + f(n) = a^2n+ba+b+an+b$

$=(a^2+a)n+(a+2)b$

if $a^2+a = 2$ and $(a+2)b=3k$, then $a=1$ or $-2$ and $b = \frac{3k}{a+2}$, giving us either

$f(n) = n+\frac{3}{(1)+2}k = n+k$ which works

or $f(n) = -2n + \frac{3}{(-2)+2}k$ which does not work

Does this give you an idea of how to find more complicated answers?

Answer 3

From the functional equation, we get $f(n)\leq 2n+3k$. We look first for other inequality of this kind. So suppose $f(n)\leq an+b$, with $a,b\in \mathbb{R}$, $a>0$. Replacing $n$ by $f(n)$ and adding $f(n)$, we get $2n+3k\leq (a+1)f(n)+b$, hence $\displaystyle f(n)\geq (\frac{2}{a+1})n+\frac{3k-b}{a+1}$. We replace $n$ by $f(n)$, we add $f(n)$, we get $\displaystyle f(n)\leq 2(\frac{a+1}{a+3})n+\frac{3ka+b}{a+3}$.

Now define two sequences by $a_0=2$, $b_0=3k$, and $\displaystyle a_{m+1}= 2\frac{a_m+1}{a_m+3}$, $\displaystyle b_{m+1}=\frac{3ka_m+b_m}{a_m+3}$. By the above, we have $f(n)\leq a_m n+b_m$ for all $n,m$.

For an explicit formula for $a_m$, as $L=1$ and $L=-2$ are the roots of the equation $\displaystyle L=2\frac{L+1}{L+3}$, we put $\displaystyle c_m=\frac{a_m-1}{a_m+2}$, and we get $\displaystyle c_{m+1}=\frac{c_m}{4}$, hence as $\displaystyle c_0=1/4$, we have $\displaystyle c_m=1/4^{m+1}$, and it is easy to see that $\displaystyle a_m=\frac{4^{m+1}+2}{4^{m+1}-1}$. Now the formula giving $b_m$ is $$(4^{m+2}-1)b_{m+1}=(4^{m+1}-1)b_m+3k(4^{m+1}+2)$$ This is "telescopic", (put $u_m=(4^{m+1}-1)b_m$) and gives $$(4^{m+1}-1)b_m=4k(4^m-1)+6k(m+1)+u_à$$

Now it is easy to see that $a_m\to 1$, and $b_m\to k$. As we have $f(n)\leq a_m n+b_m$, this gives $f(n)\leq n+k$. Replacing $n$ by $f(n)$ and adding $f(n)$, we get $2n+3k\leq 2f(n)+k$, hence $f(n)\geq n+k$, and $f(n)=n+k$ for all $n$.