If $f(f(n))+f(n)=2n+2014$, find $f$.

Question

Let the function $f:\mathbb N^{+}\to\mathbb N^{+}$ such $$f(f(n))+f(n)=2n+2014.$$

Find $f$.

My try: let $n=1$, then we have $$f(f(1))+f(1)=2016$$ let $f(1)=a$,then $$f(a)+a=2016$$ and let $n=a$, then $$f(f(a))+f(a)=2a+2014$$ so $$f(2016-a)+2016-a=2a+2014$$ so$$ f(2016-a)=3a-2$$ then I can't. Thank you.

Answer 1

Not a full solution, but hopefully a useful contribution:

Begin with the guess that $f(n) = an + b$, for $a,b \in \Bbb Z$. We have $$ f(f(n)) + f(n) = 2n + 2014 \implies\\ (a^2+a)n + (a+2)b = 2n + 2014 \implies\\ \begin{cases} a^2 + a = 2\\ (a+2)b = 2014 \end{cases} $$ Solving the first equation yields $a \in \{1,-2\}$, but only $a=1$ can work with the second equation. So, we have $$ b = 2014/(1+2) = 2014/3 \notin \Bbb Z $$ which seems to indicate that no such $f$ (i.e. no $f(n) = an + b$) exists.

In addition: if $f(n)$ is a polynomial of (finite) degree greater than $1$, then $f(f(n)) + f(n)$ must also be such a polynomial, ruling out the equality in question.

So, it seems that $f$ cannot be any polynomial on $n$ (though perhaps a valid power series exists?).

Answer 2

There is no such function. (Edit: This is a simplification of the original argument.)

The functional equation implies that $f(f(n))\leq2n+2014$ holds for all $n$. Inductively define a sequence $a_0=1$ and $a_n=f(a_{n-1})$ for $n>0$. Observe:

Lemma. For all $n$, we have $a_{2n}\leq 2015\cdot 2^n-2014$.

Proof. We prove this by induction. It is true for $n=0$. Suppose it is true for $n-1$. Then $$a_{2n}=f(f(a_{2n-2}))\leq 2a_{2n-2}+2014\leq2(2015\cdot2^{n-1}-2014)+2014=2015\cdot 2^n-2014.$$ This completes the proof. $\square$

On the other hand, our sequence satisfies a recurrence: $$a_n+a_{n-1}=f(f(a_{n-2}))+f(a_{n-2})=2a_{n-2}+2014\qquad (n\geq2)$$ This has a unique solution (with $a_0=1$ and $a_1=a:=f(1)$) $$a_n=\frac19(-2008+(2017-3a)(-2)^n+3a+6042n).$$

But $2017$ is not divisible by $3$, so the coefficient of $(-2)^n$ is nonzero. This is a contradiction, since $4^n=(-2)^{2n}$ grows faster than $2^n$, contradicting our lemma.

Answer 3

Using matrix algebra.

Let $a_0=a$, and $a_n=f\circ f\circ f\circ \ldots\circ f(a)$ where $f$ is taken $n$ times.

Then for any $n\ge 1$ we have $a_{n+1}+a_n=2a_{n-1}+2014$, or

$\begin{bmatrix} a_{n+1} \\ a_n \\ 1 \end{bmatrix}=\begin{bmatrix} -1 & 2 & 2014 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} a_n \\ a_{n-1} \\ 1 \end{bmatrix}=\ldots=\begin{bmatrix} -1 & 2 & 2014 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}^n\begin{bmatrix} f(a) \\ a \\ 1 \end{bmatrix}$

Next, you simply consider the Jordan form of the $3\times 3$ matrix, and easily find the following expression:

$a_n=\frac{3a(2+(-2)^n)+3f(a)(1-(-2)^n)+2014(3n-1+(-2)^n)}{9}$ $=\frac{a-f(a)+2014/3}{3}(-2)^n+\frac{2014}{3}n+\frac{2a+f(a)-2014/3}{3}$

and the first term will dominate at some point, making $a_n$ negative for an odd $n$. So, there is no such function.

Answer 4

This is a simplification (and then generalization to make it complicated again) of Dejan Gove's answer.

Claim. Let $A\in\mathbb N^+$, $B\in \mathbb Z$. Let $f\colon \mathbb N^+\to \mathbb N^+$ be a function with $f(f(n))+f(n)=An+B$ for all $n\in\mathbb N^+$. Then $$\frac{2B}{\sqrt{4A+1}+3} $$ is an integer.

Proof. Let $f$ be such a function and define recursively $a_{n+1}=f(a_n)$ (with $a_0\in\mathbb N^+$ arbitrary). Then the functional equation reads $$\tag1 a_{n+2}+a_{n+1}=Aa_n+B$$ If $A\ne2$ we can let $b_n:=a_n+\frac{B}{A-2}\in\mathbb Q$ and obtain $$\tag2b_{n+2}=-b_{n+1}+Ab_n$$ which is well-known to have solutions of the form $$b_n=\alpha_1 \lambda_1^n+\alpha_2\lambda_2^n$$ where $\lambda_{1,2}=\frac{-1\pm\sqrt{1+4A}}{2}$ are the (distinct real) roots of $X^2+X-A=0$ and $\alpha_{1,2}\in\mathbb R$ can be determined from the first two terms. Note that $|\lambda_2|=|\lambda_1|+1>1$. Hence if $\alpha_2\ne0$ then for $n\gg0$ we will have $|\alpha_2\lambda_2^n|>2\cdot |\alpha_1\lambda_1^n|$ and as $\lambda_2$ is negative we have $b_n\ll 0$ for large $n$ of suitable parity. But then also $a_n<0$, contradiction. Therefore $\alpha_2=0$ and $b_n=\alpha_1\lambda_1^n$. Then $\lambda_1=\frac{b_{n+1}}{b_n}$ is rational, $4A+1$ is a perfect (odd) square, so that finally $\lambda_1\in\mathbb N^+$. From $b_{n+1}=\lambda_1b_n$ we find $$ a_{n+1}=\lambda_1a_n+\frac{(\lambda_1-1)B}{A-2}$$ We conclude that $$ \frac{(\lambda_1-1)B}{A-2}=\frac{(\sqrt{4A+1}-3)B}{2(A-2)}=\frac{2B}{\sqrt{4A+1}+3}$$ is an integer.

If $A=2$, we can let $b_n=a_n-\frac{Bn}3$ instead and obtain $(2)$ again, with solutions of the form $b_n=\alpha_1(-2)^n+\alpha_2$ so that again $a_n=\alpha_1(-2)^n+\alpha_2+\frac{Bn}3\ll 0 $ for $n$ large enough of suitable parity - unless $\alpha_2=0$. We conclude $a_n=\alpha_2+\frac{Bn}{3}$ so that $\frac B3=a_{n+1}-a_n$ is an integer. $_\square$

Corollary. If a function as above exists, then $A=(d-1)(d-2)$ for a divisor $d\mid B$ with $d\ge3$. Specifically, if $A=2$ then $3\mid B$.

Proof. This follows from writing $4A+1$ as odd perfect square. $_\square$