2

Let $N \in \mathbb{N}$ be constant. Find all non-decreasing functions $f:\mathbb{Z} \rightarrow \mathbb{Z}$ satisfying $$f(n) + f(n+1) + ... + f(n+N-1) = n$$ for all integers $n$.

Please check my solution.

$$ f(n) + f(n+1) + ... + f(n+N-1) = n \tag{1} $$

$$ f(n+1) + f(n+2) + ... + f(n+N) = n+1 \tag{2} $$

(2)-(1):

$$ f(n+N) - f(n) = 1 $$

As $f$ are non-decreasing function, so $\{f(n+1), f(n+2), ..., f(n+N-1)\} \in \{f(n)$ or $f(n)+1\}$

If $f(n+l), f(n+l+1), ...,f(n+N-1) = f(n)+1$

and $f(n+l)$ has the smallest value that is equal to $f(n)+1$

then $f(n+l-N), f(n+l+1-N), ..., f(n-1) = f(n)$

and $f(n), f(n+1), ..., f(n+l-1) = f(n)$

There would exist $k\in \mathbb{N}$ such that $f(k), f(k+1), ..., f(k+N-1)$ are all equal

and the solution would be $k\cdot f(n)+(N-k)(f(n)+1)=n$

i.e., $f(n) = \frac{n-N+k}{N}$, Contradiction

Therefore, $\{f(n+1), f(n+2), ... , f(n+N-1)\}$ are all equal where $n \equiv 0 (\bmod N)$

My answer is $f(n) = \left\lfloor \frac{n}{N} \right\rfloor$ where $n\in \mathbb{Z}$

Check :

Let $\left\lfloor \frac{n}{N} \right\rfloor = l, n = Nl+t$

$\Rightarrow f(n)=f(n+1)=...=f(n+N-2-t)=l$

$f(n+N-1-t)=f(n+N-1) = ...=f(n+N-1)$

so $f(n)+f(n+1)+...+f(n+N-1) = l(N-1-t) + (l+1)(1+t) = Nl +t $

caverac
  • 19,345
user403160
  • 3,286

1 Answers1

2

Your solution for $k$ is not very clear and I don't think it's entirely correct:

There would exist $k\in\mathbb N$ such that $f(k),f(k+1),...,f(k+N−1)$ are all equal and the solution would be $k⋅f(n)+(N−k)(f(n)+1)=n$

i.e., $f(n) = \frac{n-N+k}{N}$, Contradiction

It looks like the factors $k$ and $(N-k)$ is the numder of terms that are $f(n)$ and $f(n+1)$ respectively. But that can't be like that since that number would depend on $n$. (Besides a contradiction here would indicate that we have no solutions as the existence of the solution is basically the only hypothesis we've introduced).

Let's step back and see what we have. We have concluded that there is a $k$ such that $f(k+j)$ is constant ($0\le j<N$), we can also see that $f(n+jN) = f(n)+j$. So what we basically have is a function that steps one step every $N$ integers. We also see by this that we can have $0\le k< N$ and that $f$ is a function on the form

$$f(n) = \left\lfloor {n-k\over N}\right\rfloor + c$$

Now to determine $k$ and $c$ we consider the sum

$$\sum_0^{N-1}f(j) = 0$$

We use that $f(j) = c-1$ if $j<k$ and $c$ otherwise so we have $$\sum_0^{N-1}f(j) = k(c-1) + (N-k)c = Nc - k = 0$$

Now since $0\le k<N$ we have $-Nc \le k-Nc = 0 < N-Nc$ and especially that $Nc \ge 0 > N(c-1)$ So we have $1>c\ge 0$ so $c=0$ and therefore also $k=0$.

So at least your conclusion is correct, the only such function is:

$$f(n) = \left\lfloor{n\over N}\right\rfloor$$

skyking
  • 16,654
  • Thank you, skyking. I'm not good at Functional equation. Can you please point out the error in my work ? – user403160 Jul 18 '17 at 13:52
  • @carat I've updated the answer highlighting the part that I suspect is incorrect. – skyking Jul 18 '17 at 14:25
  • I think "There would exist k∈N such that f(k),f(k+1),...,f(k+N−1) are all equal" is correct. But after that, I'm not sure. Please suggest. – user403160 Jul 18 '17 at 16:46
  • @carat I don't think there's more to it, AFAICS $k$ can be any number which leads to $\lfloor (n-a)/N\rfloor$ are all valid solutions. – skyking Jul 18 '17 at 20:10
  • What is range of $a$ ? – user403160 Jul 19 '17 at 03:21
  • @carat It's $\mathbb Z$. Originally I was considering writing it as $\lfloor (n-a)/N\rfloor+b$ that is one constant to set the step location and one to shift $y$ offset, but I realized that $a$ can be used for both. – skyking Jul 19 '17 at 05:01
  • In case $n = 0$, $f(0)+f(1)+...+f(N-1) = 0$, i.e., $ \left\lfloor \frac{-a}{N} \right \rfloor + \left \lfloor \frac{-a+1}{N} \right \rfloor +...+ \left \lfloor \frac{-a+N-1}{N} \right \rfloor = 0$ This is not true for large $a$ so it's not true for all $a\in \mathbb{Z}$ – user403160 Jul 19 '17 at 06:43
  • @carat I forgot the initial requirements, these functions only fulfil the requirement that $f(n+N)-f(n)=1$ and that $f$ is non-decreasing. The original requirement will mean that $a=0$. I've updated the answer. – skyking Jul 19 '17 at 08:01
  • Thank you for your explanation. So the answer is $f(n) = \left\lfloor \frac{n}{N} \right\rfloor$ for all $n \in \mathbb{Z}$, correct ? – user403160 Jul 19 '17 at 11:51
  • @carat Yes, I've updated the answer with the result (which is the same as you've got) – skyking Jul 19 '17 at 12:01
  • Thank you very much, skyking.:) – user403160 Jul 19 '17 at 12:09