Find all functions $f: \mathbb{N}\to \mathbb{N}$ such that for all $n\in \mathbb{N}$: \[f(f(n))+f(n)=2n+2001 \text{ or }2n+2002.\]
Problem
Source:
Tags: function, Functional Equations
BaBaK Ghalebi
24.09.2007 01:54
I think the following one holds: the only function satisfying: $ i)f:\mathbb{N}\to\mathbb{N}$ $ ii)\forall n\in\mathbb{N}: f(f(n))+f(n) = 2n+k$ is $ f(n) = n+\frac{k}{3}$ thus we must have $ 3\mid k$ so we must have $ f(f(n))+f(n) = 2n+2001$ and the only solution is $ f(n) = n+\frac{2001}{3}$ so for every natural number $ n$ we have: $ f(n) = n+667$
Peter
24.09.2007 23:40
Can you please be more detailed? How do you know only $ 2001$ can work? The problem you cite is not the same as the given problem (nor stronger).
BaBaK Ghalebi
25.09.2007 01:07
well,if for every natural $ n$ we had $ f(f(n))+f(n)=2n+2001$,according to the problem that I sent we have $ f(n)=n+667$ also if for every natural $ n$ we had $ f(f(n))+f(n)=2n+2002$ then according to the problem posted by me we must have $ 3\mid 2002$ which isnt possible,so in this case we have no solutions... I had this idea in mind when I posted that problem,but now I see that it doesnt completely solve the problem... but I have found the following solution,which I will post in the hidden section below:
enescu wrote:
We define the sequence of positive integers $ \left( a_{n}\right)_{n\geq0}$
as follows: $ a_{0}$ is an arbitrary positive integer and $ a_{n+1}= f\left( a_{n}\right) ,$ for all $ n.$ Let
\[ c_{n}=a_{n}-a_{n-1}-667,\]
for all $ n\geq1.$ Then
\[ c_{n+1}+2c_{n}=a_{n+1}+a_{n}-2a_{n-1}-2001,\]
therefore for all $ n\geq1,$ $ c_{n+1}+2c_{n}$ is an integer, satisfying
\[ 0\leq c_{n+1}+2c_{n}\leq1.\]
Suppose that $ c_{1}> 0;$ then $ c_{1}\geq1$ and $ c_{2}\leq-2c_{1}+1\leq-1.$
Moreover, $ c_{3}\geq-2c_{2}\geq2.$ We claim that $ c_{2k+1}\geq2^{k}$ and we prove it by induction$ .$ If $ c_{2k+1}\geq2^{k}$ holds, then $ c_{2k+2}\leq-2c_{k+1}+1\leq-2^{k+1}+1$ and $ c_{2k+3}\geq-2c_{k+2}\geq2^{k+2}-2\geq2^{k+1},$ and the claim is proved.
Observe that
\[ a_{2k+2}-a_{2k}-1334=c_{2k+2}+c_{2k+1}\leq-2^{k}+1,\]
therefore, for $ k\geq11,$ we have
\[ a_{2k+2}<a_{2k}.\]
This is a contradiction, since all $ a_{k}$'s must be positive integers.
If $ c_{1}< 0,$ then $ c_{2}\geq-2c_{1}> 0$ and we repeat our argument until we obtain
\[ a_{2k+3}<a_{2k+1},\]
for all $ k\geq11,$ another contradiction.
We conclude that $ c_{1}= 0,$ that is, $ a_{1}= a_{0}+667.$ It follows that
\[ f\left( n\right) =n+667,\]
for all $ n.$
Peter
25.09.2007 09:37
And... enescu's solution is also for the case 2001, no? I see no 2002 appearing in it?
BaBaK Ghalebi
25.09.2007 16:29
enescu wrote: therefore for all $ n\geq1,$ $ c_{n+1}+2c_{n}$ is an integer, satisfying \[ 0\leq c_{n+1}+2c_{n}\leq1.\] yeah at this step... note that we have: $ c_{n}= a_{n}-a_{n-1}-667$ therefore we have: $ c_{n+1}= a_{n+1}-a_{n}-667$ and also: $ 2c_{n}= 2a_{n}-2a_{n-1}-2\times 667$ $ \Rightarrow c_{n+1}+2c_{n}= a_{n+1}+a_{n}-2a_{n-1}-2001$ but according to the problem we know that: $ f(f(n))+f(n) = 2n+2001$ or $ f(f(n))+f(n) = 2n+2002$ so we have either $ a_{n+1}+a_{n}= 2a_{n-1}+2001$ or $ a_{n+1}+a_{n}= 2a_{n-1}+2002$ which gives us: $ a_{n+1}+a_{n}-2a_{n-1}-2001 = 0$ or $ a_{n+1}+a_{n}-2a_{n-1}-2001 = 1$ so we have: $ c_{n+1}+2c_{n}= 0$ or $ c_{n+1}+2c_{n}= 1$ but $ c_{n}$ is an integer so the last statement is equivalent to: $ 0\leq c_{n+1}+2c_{n}\leq 1$ and the conclusion follows...