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.

  • $\begingroup$ Is this a competition problem? $\endgroup$ – Matias Heikkilä Nov 18 '15 at 13:45
  • $\begingroup$ What's the source of the problem? (It's not a recurrence relation, by the way, and those tools are unlikely to be useful.) $\endgroup$ – mrf Nov 18 '15 at 13:58
  • $\begingroup$ @mrf Actually, recurrence relations can be useful. A technique that often works for problems such as this one is to consider (for some fixed $n$) the values of $n, f(n), f(f(n)), f(f(f(n))), \cdots$. This sequence does satisfy some non-homogeneous linear recurrence relation, and the tools for solving such relations can then be applied to get some information about the function $f$. $\endgroup$ – Dylan Nov 19 '15 at 11:17

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$.


The simplest possible answer is:

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

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


$f(f(n)) + f(n) = a^2n+ba+b+an+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?

  • 1
    $\begingroup$ If $f(n)=2n+(3/2)k$ then $f(f(n))+f(n)=6n+6k.$ $\endgroup$ – coffeemath Nov 18 '15 at 15:56
  • 2
    $\begingroup$ I see that at one step you calculated $f(f(n))-f(n).$ However in the post the left side is $f(f(n))+f(n).$ $\endgroup$ – coffeemath Nov 18 '15 at 17:01
  • 1
    $\begingroup$ I need to start drinking coffee in the morning. Thank you, editing now. $\endgroup$ – Simpson17866 Nov 18 '15 at 17:18

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.