\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/~njas/sequences/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}


\begin{center}
\vskip 1cm{\LARGE\bf A Curious Bijection on Natural Numbers}

\vskip 1cm
\large
B. J. Venkatachala\\
MO Cell, HBCSE(TIFR)\\
Department of Mathematics \\
Indian Institute of Science \\
Bangalore-560012 \\
India \\
\href{mailto:jana@math.iisc.ernet.in}{\tt jana@math.iisc.ernet.in} \\
\end{center}

\newenvironment{pf}{\noindent{\bf Proof. }}{\hfill{$\Box$} }
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\l{\lambda}
\def\N{\mathbb N}
\newtheorem{thm}{Theorem}
%\newtheorem{corollary}[thm]{Corollary}
%\newtheorem{lemma}{Lemma}

\vskip .2 in

\begin{abstract}
We give a greedy algorithm for describing an enumeration of the set of all
natural numbers such that the sum of the first $n$ terms of the
sequence is divisible by $n$ for each natural number $n$.  We show
that this leads to a bijection $f$ of the set of all natural
numbers onto itself that has some nice properties.  We also show 
that the average function  of the first $n$ terms of the
sequence satisfies a functional equation which completely describes
all the properties of the function $f$. In particular, $f$ turns out to
be an {\em involution\/} on the set of all natural numbers.  
\end{abstract}


\section{Introduction}

The following problem was posed by A. Shapovalov \cite{ShQ96}:

\begin{center}
\begin{minipage}[t]{4.2in}
{\it Does there exist a sequence of positive integers containing each
positive integer exactly once such that the sum of the first $k$ terms is
divisible by $k$ for each $k=1,2,3, \ldots $?}
\end{minipage}
\end{center}

\noindent The published solution, though ingenious, is not intuitive.
Shapovalov inductively defines a sequence $\langle a_n \rangle $,
which appears as a sequence \seqnum{A019444} in Sloane's
Encyclopedia of Integer Sequences \cite{Sloane}, as follows.
Put $a_1 =1$ and having
defined $a_1, a_2, \ldots, a_k$, first compute $n_k =\big(
a_1+a_2+\cdots +a_k)/k$. Now define
$$
a_{k+1} =\begin{cases}
         n_k,& \text{ if $n_k$ is not already in the set $\big\{ a_1, a_2,
\ldots , a_k\big\}$};\\
n_k+k+1, &\text{ if $n_k$ is  in the set $\big\{ a_1, a_2,
\ldots , a_k\big\}$}.
\end{cases}
$$
It is not clear, a priori, that $n_k$ is an integer --
which is necessary to conclude that
$k$ divides $ a_1+a_2+\cdots +a_k$. The proposer first proves this by
induction and then proceeds to prove that such a sequence indeed has the
required property.


Equivalently one has to find a bijection
$f$ on $\N$, the set of all natural numbers, such that $n$ divides
$f(1)+f(2)+\cdots +f(n)$ for each $n$. A natural approach is the so
called the {\em greedy algorithm\/}. One can start with $f(1)=1$ and
having defined $f(j)$ for $1\leq j\leq n$, the choice for $f(n+1)$ is
the least positive integer $l$, not in the set $\big\{ f(1), f(2),
\ldots , f(n)\big\}$, such that $(n+1)$ divides $f(1)+f(2)+\cdots
+f(n)+l$. Since $f(1)=1$, the value of $f(2)$ cannot be equal to 1
although $f(1)+1$ is divisible by 2. The natural choice is $f(2)=3$,
for then 3 is not yet assumed by the function $f$ and $1+3=4$ is
divisible by 2. Since $f(1)+f(2)+2=6$ is divisible by 3 and 2 is not
in the set $\big\{ f(1), f(2)\big\}$, the algorithm proposes $f(3)=2$.
Now, although $f(1)+f(2)+f(3)+2=8$ is divisible by 4, it is not
possible to choose $f(4)=2$ since 2 is already in the set $\big\{
f(1),f(2), f(3)\big\}$. However if we add 4 more, then $8+4=12$ is
also divisible by 4 and $2+4=6$ is not in the set $\big\{ f(1),f(2),
f(3)\big\}$. Thus it is natural to choose $f(4)=6$. A similar
reasoning shows that $f(5)$ may be chosen 8 and $f(6)$ may be chosen
4. This process can be continued to compute $f(n)$ for at least small
values of $n$. The following table gives an idea how the {\em greedy
algorithm\/} works and the nature of $f(n)$ for small $n$. The table
also includes the {\em average function\/} $\displaystyle h(n)=\frac{
f(1)+f(2)+\cdots +f(n)}{n}$.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
$n$&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19\\ \hline
$f(n)$&1&3&2&6&8&4&11&5&14&16&7&19&21&9&24&10&27&29&12\\ \hline
$h(n)$&1&2&2&3&4&4&5&5&6&7&7&8&9&9&10&10&11&12&12 \\ \hline
\end{tabular}
\end{center}

There are some interesting properties of the functions $f(n)$ and $h(n)$ 
as evident from
the table, some are simple and some are more deep. In fact we have the following results.
\begin{lemma}
\label{lem:1}
Let $f$ and $h$ be functions defined on $\N$  as above. Then
\begin{enumerate}
\item[({\bf I})]
$h$ is a nondecreasing function on ${\N}$ and $h(n)\leq n$;
\item[({\bf II})]
$h(n+1)=h(n)$ or $h(n)+1$, for all $n\in \N$;
\item[({\bf III})]
$h(n+1)=h(n) \Longleftrightarrow f(n+1)=h(n)$, for all $n\in \N$;
\item[({\bf IV})]
$h(n+1)=h(n)+1 \Longleftrightarrow f(n+1)=h(n)+n+1$, for all $n\in \N$.
\end{enumerate}
\end{lemma}

Much deeper properties of the functions $f$ and $h$ are given by
Theorem \ref{thm:1}.
\begin{thm}
\label{thm:1}
The functions $f$ and $h$ also satisfy, for all $n\in \N$, 
\begin{enumerate}
\item[({\bf V})]
$h\big(h(n)\big)+h\big(n+1\big) =n+2$;
\item[({\bf VI})]
$f\big(f(n)\big)=n$;
\item[({\bf VII})]
$h\big(h(n)+n\big)=n+1$.
\end{enumerate}
\end{thm}

A close look at this way of defining $f$ and Shapovalov's sequence
$\langle a_n\rangle $ shows that $f(n)=a_n$. Indeed $a_{k+1}$ is
defined using the previous average $ n_k$: $a_{k+1}=n_k$ if $n_k$ is
not already $a_j$ for some $j\leq k$; and $a_{k+1}=n_k +k+1$ if $n_k$
is used up to define some $a_j$. This is precisely forced in greedy
algorithm, but one need to prove it. The table also exhibits some nice
properties of $h$ and $f$.  The most intriguing are ({\bf V}), ({\bf
VI}) and ({\bf VII}). In particular the property ({\bf VI}) shows that $f$
is indeed a bijection. We prove all these in the sequel.

The involutive property of $f$ is mentioned in \cite{Sloane}. Apart
from this, no other property is mentioned in the literature  to the
best knowledge of author.

Among several properties of the functions
$h$ and $f$ as stated in Theorem \ref{thm:1}, is it possible to single out a
particular property which tells about the remaining ones? It turns out that
({\bf V}) is indeed one such property. In fact it completely describes
all the rest. It is not surprising in view of the fact that the
functional equation
$$
h\big(h(n)\big)+h(n+1)=n+2,
$$
for all $n\in {\N}$, uniquely determines the function $h$. The
surprising fact is that this function is related to the {\em Golden
Ratio\/} $\alpha$, given by $\alpha =(1+\sqrt{5})/2$. In fact, one can
show that $h(n)=\lfloor n\alpha\rfloor -n+1$, where $\lfloor x\rfloor
$ denotes the greatest integer not exceeding $x$; \cite{BjvFeq02}.
However, without actually computing $h(n)$ explicitly, it is possible
to show that the above relation directly leads to a bijection of the
desired type. The following theorem elucidates these facts. 

\begin{thm}
\label{thm:2}
Suppose $h:{\N}\to {\N}$ is a function such that
\begin{equation}
\label{eq:eq1}
h\big(h(n)\big)+h(n+1)=n+2,
\end{equation}
holds for all $n\in {\N}$. Define $f:{\N}\to {\N}$ by $f(1)=1$ and
$$
f(n+1)=\begin{cases}
       h(n),& \text{ if $h(n+1)=h(n)$};\\
       h(n)+n+1,& \text{ if $h(n+1)=h(n)+1$}.
       \end{cases}
$$
Then $f$ is a bijection on ${\N}$ such that for each
$n\in{\N}$, the sum $f(1)+f(2)+\cdots + f(n)$ is divisible by $n$.
\end{thm}

Thus the functional equation (\ref{eq:eq1}) on $\N$ uniquely
determines a function $h$ on $\N$ and this leads to a bijection $f$ on
$\N$ such that for every  natural number $n$ the sum $f(1)+f(2)+\cdots
+f(n)$ is divisible by $n$, which was sought by Shapovalov. 

\section{Proof of Lemma 1}

We prove some simple properties of $f$ and $h$ in this section,
as stated in Lemma \ref{lem:1}.  

\begin{pf}
 We use induction on $n$. These are easy to verify for
$n=1,2$ using the table of values of $f$ and $h$ given earlier.
Suppose these hold for all $j$, where $1\leq j\leq n$. Thus we have
$h(j)\leq j$, for $1\leq j\leq n$; $h(j+1)=h(j)$ or $h(j)+1$, for
$1\leq j\leq n-1$. This in particular implies that $h(1)\leq h(2)\leq
\cdots \leq h(n)$. Moreover $f(j+1)=h(j)\Longleftrightarrow
h(j+1)=h(j)$, for $1\leq j\leq n-1$ and $f(j+1)=h(j)+j+1
\Longleftrightarrow h(j+1)=h(j)+1$, for $1\leq j\leq n-1$. Let $l$ be
the least positive integer such that $(n+1)$ divides $f(1)+f(2)+\cdots
+f(n)+l$. Thus
$$
(n+1)k =f(1)+f(2)+\cdots +f(n)+l =nh(n)+l,
$$
for some $k$. Since $nh(n)+h(n)$ is divisible by $(n+1)$, the definition of
$l$ implies that $l\leq h(n)$. Suppose, if possible, $l<h(n)$. Then
$nh(n)+l$ and $nh(n)+h(n)$ are both divisible by $(n+1)$, and
$$
nh(n)<nh(n)+l < nh(n)+h(n).
$$
Thus we see that $h(n)-l$ is divisible by $n+1$. This forces $h(n)-l
\geq n+1$ contradicting the induction hypothesis $h(n)\leq n$.
We conclude that $l=h(n)$. In
other words, the least positive integer $l$ such that $(n+1)$ divides
$f(1)+f(2)+\cdots +f(n)+l$ is equal to $h(n)$, the average of
$f(1)+f(2)+\cdots +f(n)$. 

If $h(n)$ does not belong to the set $\big\{ f(1), f(2), \ldots ,
f(n)\big\}$, then the definition of $f(n+1)$, via the greedy algorithm,
shows that $f(n+1)=h(n)$. If $h(n)$ is already in the set $\big\{
f(1),f(2), \ldots ,f(n)\big\}$, then we consider $h(n)+n+1$. Obviously
$f(1)+f(2)+\cdots +f(n)+h(n)+n+1$ is a multiple of $(n+1)$. It is our
intention to prove that $h(n)+n+1$ is not in the set $\big\{f(1),f(2),
\ldots ,f(n)\big\}$. Suppose to the contrary that $h(n)+n+1$ lies in the
set $\big\{f(1),f(2), \ldots ,f(n)\big\}$. Then $h(n)+n+1=f(j)$ for
some $j\leq n$. Induction hypothesis shows that $f(j)=h(j-1)$ or
$h(j-1)+j$. If the first alternative holds, then
$$
h(n)+n+1 =f(j)=h(j-1)\leq j-1 <n,
$$
a clear contradiction. If on the other hand $f(j)=h(j-1)+j$, then
$$
h(n)+n+1=h(j-1)+j.
$$
This forces $h(n)-h(j-1)=j-n-1<0$, which is impossible since $h(j-1)\leq h(n)$
by induction hypothesis. Thus $h(n)+n+1$ is not an element of
$\big\{f(1),f(2), \ldots ,f(n)\big\}$. It follows that $h(n)+n+1$ is the
least positive integer $l$ not in the set $\big\{f(1),f(2), \ldots
,f(n)\big\}$ such that $(n+1)$ divides $f(1)+f(2)+\cdots +f(n)+l$. By
definition  $f(n+1)=h(n)+n+1$.

Thus $f(n+1)=h(n)$ or $h(n)+n+1$. In the first case
$$
h(n+1)=\frac{f(1)+f(2)+\cdots +f(n)+h(n)}{n+1} =\frac{nh(n)+h(n)}{n+1}=h(n).
$$
Similarly $h(n+1)=h(n)+1$ in the second case. On the other hand,
$h(n+1)=h(n)$ forces $f(n+1)=h(n)$ and $h(n+1)=h(n)+1$ implies that
$f(n+1)=h(n)+n+1$.  It may also be observed that $h(n+1)=h(n)$ or $h(n)+1$
gives $h(n)\leq h(n+1)$ and $h(n+1)\leq n+1$. This proves inductive step and
the properties ({\bf I})-({\bf IV}) are true for all values of $n$.
\end{pf}


\section{Some more consequences} 

Here are some more consequences of
the definition and the properties proved in Lemma \ref{lem:1}. These ar useful
in completing the proof of Theorem \ref{thm:1}.

\begin{itemize}
\item {\em The function $h$ does not assume the same value at three
consecutive integers and hence it does not assme the same value at
three distinct integers. Consequently $h(n+2)>h(n)$ for all $n\geq
1$.\/}

Since $h$ is a nondecreasing function of $n$, we have
$h(n)\leq h(n+1)\leq h(n+2)$. If $h(n+2)=h(n+1)$, then $f(n+2)=h(n+1)$
and hence $h(n+1)$ is not in the set $\big\{ f(1), f(2), \ldots, f(n),
f(n+1)\big\}$, by definition.  But $h(n+1)=h(n)$ implies that
$f(n+1)=h(n)=h(n+1)$ showing that $h(n+1)$ is an element of the set
$\big\{ f(1), f(2), \ldots, f(n), f(n+1)\big\}$. (In fact equal to
$f(n+1)$.) This contradiction proves the statement.

\item {\em The function $h$ is surjective.\/}

This follows from the fact that $h$ is nondecreasing, it increases in steps
of 0 or 1 and $h(n+2)>h(n)$ for all $n\geq 1$.

\item {\em The function $f$ is surjective.\/}

Take any $m\in {\N}$, and let $m=h(k)$. Such a $k$ exists because $h$
is surjective. Then either $h(k)$ belongs to the set $\big\{ f(1),
f(2)\ldots , f(k)\big\}$ or $f(k+1)=h(k)$. Thus $m$ is in the range of
$f$.

\item {\em The function $f$ is one-one.\/}

Suppose $f(m)=f(k)$ for some $m<k$. The property ({\bf IV}) of $f$
shows that $f(k)=h(k-1)$ or $h(k-1)+k$. If $f(k)=h(k-1)$, then
$f(m)=h(k-1)$ belongs to the set $\big\{f(1), f(2), \ldots ,
f(m)\big\}$ which itself is a subset of $\big\{f(1), f(2), \ldots ,
f(k-1)\big\}$, as $m\leq k-1$. By definition of $f$, it follows
$f(k)=h(k-1)+k$ contradicting $f(k)=h(k-1)$.

Suppose on the
other hand $f(k)=h(k-1)+k$. Now $f(m)=h(m-1)$ or $h(m-1)+m$. Since
$m-1<k-1$, we have $h(m-1)\leq h(k-1)$ and hence
$$
h(m-1)=f(m)=f(k)=h(k-1)+k
$$
is impossible. If $h(k-1)+k=h(m-1)+m$, we have 
$$
h(k-1)-h(m-1) =m-k<0,
$$
which again is impossible since $h(m-1)\leq h(k-1)$. Thus $f(m)\neq f(k)$ if
$m\neq k$.

\item {\em The inequality $h(n)\leq n-2$ holds for all $n\geq
6$.\/}

This follows from the observation $h(6)=4$ and and by an easy induction using
the fact that $h$ increases in steps of 0 or 1.

\item {\em If $f(n+1)>h(n)$, then $f(j)>h(n)$ for all $j\geq
n+1$.\/}

In fact
\begin{eqnarray*}
f(n+2) \geq h(n+1) &=&\frac{f(1)+f(2)+\cdots + f(n+1)}{n+1}\\
&=& \frac{nh(n)+f(n+1)}{n+1}\\
&>&h(n).
\end{eqnarray*}
An easy induction proves that $f(j)>h(n)$ for all $j\geq n+1$.

\item {\em There are no integers $k\geq 2$ and $l$ such that $f(k-1)=l$ and
$f(k)=l+1$. In other words, $f$ does not assume consecutive values at
consecutive integers.\/}

Suppose such a pair $k\geq 2$ and $l$ exist. We may assume $k>2$, for this
result is immediate for $k=2$. Thus
$f(k)=f(k-1)+1$ and hence
\begin{eqnarray*}
kh(k)&=& f(1)+f(2)+\cdots + f(k)\\
&=& f(1)+f(2)+\cdots + f(k-2)+2f(k-1)+1\\
&=& (k-2)h(k-2)+2f(k-1)+1.
\end{eqnarray*}
This implies that
$$
k\big(h(k)-h(k-2)\big) =-2h(k-2)+2f(k-1)+1.
$$
Now $h(k)-h(k-2)=1$ or 2, since $h$ does no assume the same value at
three consecutive integers. It cannot be equal to 2, for then
left side is even and right side is odd. Thus $h(k)=h(k-2)+1$ and hence
\begin{eqnarray*}
k&=& -2h(k-2)+2f(k-1)+1\\
&=& 2\big( f(k-1)-h(k-2)\big)+1.
\end{eqnarray*}
But $f(k-1)=h(k-2)$ or $h(k-2)+k-1$. In both the cases $k=1$ contradicting
$k>2$.
\end{itemize}

\section{ Proof of Theorem 1}

We 
prove the deeper properties of $h$ and $f$ as stated in Theorem
\ref{thm:1}. The following properties hold for all values of $n\in \N$:

\begin{enumerate}
\item[({\bf V})]
$h\big(h(n)\big)+h\big(n+1\big) =n+2$;
\item[({\bf VI})]
$f\big(f(n)\big)=n$;
\item[({\bf VII})]
$h\big(h(n)+n\big)=n+1$.
\end{enumerate}

\noindent
We use induction to prove these statements. 
 For $n=1$, it is a routine verification:
$$
f(1)=1, h(1)=1, h(2)=2, h(1)+1 =2;
$$
hence
$$
h\big(h(n)\big)+h\big(n+1\big)=h\big(h(1)\big)+h\big(2\big)=h(1)+h(2)=3=n+2;
$$
$$
f\big(f(n)\big)=f\big(f(1)\big)=f\big(1\big)=1=n;
$$
$$
h\big(h(n)+n\big)= h\big(h(1)+1\big)=h\big(2\big)=2=n+1.
$$
These may also be verified for $n=2,3,4,5,6$. So we assume that $m>
6$ and ({\bf V})-({\bf VII}) are true for all $n\leq m$. We prove them
for $n=m+1$. We have to prove  three statements:
\begin{enumerate}
 \item[({\bf a})] $ h\big(h(m+1)\big)+h\big(m+2\big)=m+3$;
\item[({\bf b})]$f\big(f(m+1)\big)=m+1$;
\item[({\bf c})] $h\big(h(m+1)+m+1\big)=m+2$.
\end{enumerate}


\vspace{10pt}

 {\bf Proof of} ({\bf a}):  We have either  $h(m+1)=h(m)$ or $h(m+1)=h(m)+1$. If
$h(m+1) = h(m)+1$, we have two  possibilities:
$h(m+2)=h(m+1)$ or $h(m+2)=h(m+1)+1$. We consider these three cases
separately.   

 Case (i).
Suppose $h(m+1)=h(m)$.  Since $h$ does not take the same value at
three consecutive integers, it follows that $h(m+2)$ cannot
be equal to $h(m+1)$. Hence $h(m+2)=h(m+1)+1$. Induction hypothesis gives
\begin{eqnarray*}
h\big(h(m+1)\big)+h\big(m+2\big) &=& h\big(h(m)\big)+h\big(m+1\big)+1\\
&=& (m+2)+1 =m+3.
\end{eqnarray*}

 Case (ii). Suppose on the other hand $h(m+1)=h(m)+1$, but $h(m+2)=h(m+1)$. Here
we have  either $h\big(h(m)+1\big)= h\big(h(m)\big)$ or $h\big(h(m)+1\big)= h\big(h(m)\big)+1$.
If $h\big(h(m)+1\big)= h\big(h(m)\big)$, then it must be the case that
$h\big(h(m)+2\big)= h\big(h(m)+1\big)+1$; otherwise $h$ assumes the same
value at three consecutive integers $h(m)$, $h(m)+1$ and $h(m)+2$. Thus
using the property ({\bf IV}), we obtain
\begin{eqnarray*}
f\big(h(m)+2\big)&=& h\big(h(m)+1\big)+h(m)+2\\
&=& h\big(h(m)+1\big)+h(m+1)+1\\
&=& h\big(h(m)\big)+h(m+1)+1\\
&=& (m+2)+1 \\
&=&m+3,
\end{eqnarray*}
where induction hypothesis is invoked. But $h(m)+2 \leq m$ for $m\geq 6$.
Again by induction hypothesis, we get
$$
f\Big(f\big(h(m)+2\big)\Big) =h(m)+2.
$$
It follows that
\begin{eqnarray*}
f(m+3)&=& h(m)+2\\
&=& h(m+1)+1= h(m+2)+1.
\end{eqnarray*}
But this is impossible, since either $f(m+3)=h(m+2)$ or $h(m+2)+m+3$. We
conclude that $h\big(h(m)+1\big)= h\big(h(m)\big)$ is not possible.

Thus we must have  $h\big(h(m)+1\big)= h\big(h(m)\big)+1$. In this case
\begin{eqnarray*}
h\big(h(m+1)\big)+h\big(m+2\big)&=&h\big(h(m)+1\big)+h(m+1)\\
&=&h\big(h(m)\big)+1 +h(m+1)\\
&=&(m+2)+1 =m+3,
\end{eqnarray*}
where again induction hypothesis that $h\big(h(m)\big)+h(m+1)=m+2$ is used.

 Case (iii).  Suppose $h(m+1)=h(m)+1$ and $h(m+2)=h(m+1)+1$.  Here again we
have two possibilities:  $h\big(h(m)+1\big)=
h\big(h(m)\big)$ or  $h\big(h(m)+1\big)=
h\big(h(m)\big)+1$.

If $h\big(h(m)+1\big)= h\big(h(m)\big)$ holds, we have 
\begin{eqnarray*}
h\big(h(m+1)\big)+h\big(m+2\big)&=&h\big(h(m)+1\big)+h(m+1)+1\\
&=&h\big(h(m)\big) +h(m+1)+1\\
&=&(m+2)+1 =m+3,
\end{eqnarray*}
using $h\big(h(m)\big)+h(m+1)=m+2$.

If on the other hand $h\big(h(m)+1\big)=
h\big(h(m)\big)+1$, then the property ({\bf IV}) shows that
\begin{eqnarray*}
f\big(h(m)+1\big)&=& h\big(h(m)\big)+h(m)+1\\
&=& h\big(h(m)\big)+h(m+1)\\
&=&m+2.
\end{eqnarray*}
Since $h(m+1)\leq m$, induction hypothesis gives
$$
h(m+1)=f\Big(f\big(h(m+1)\big)\Big) =f(m+2).
$$
But then ({\bf III}) implies that $h(m+2)=h(m+1)$ contradicting $h(m+2)=h(m+1)+1$.
Thus the case $h\big(h(m)+1\big)=h\big(h(m)\big)+1$ cannot occur when
$h(m+1)=h(m)+1$ and $h(m+2)=h(m+1)+1$. 

This completes the proof of  ({\bf V}) for $n=m+1$.

\medskip
{\bf Proof of} ({\bf b}):
Here again there are two cases: $f(m+1)=h(m)$ or $f(m+1)=h(m)+m+1$.

Case (i).
Suppose $f(m+1)=h(m)$. By the property  ({\bf III}), we have
$h(m+1)=h(m)$. Put $j=h(m)-1$. Since $h(m+1)=h(m)$ and $h$ does not
assume the same value at three consecutive integers,  we must have 
$h(m)=h(m-1)+1$. Thus $j+1=h(m)=f(m+1)$ and
\begin{eqnarray*}
h(j+1)+j&=&h\big(h(m)\big) +h(m)-1\\
&=&h\big(h(m)\big)+h(m+1)-1\\
&=&m+1;
\end{eqnarray*}
we have used induction hypothesis that $h\big(h(m)\big)+h(m+1)=m+2$.

Suppose, if possible, $h(j+1)=h(j)$. Then $h(j)+j=h(j+1)+j=m+1$ and
hence
$$
h\big(h(m)-1\big)+h(m)-1=m+1.
$$
Now $h(m)-1=h(m-1)$ and hence
$$
h\big(h(m)-1\big)+h(m)-1
=h\big(h(m-1)\big)+h(m)-1=(m+1)-1=m,
$$
by induction hypothesis. Thus we obtain an  absurd conclusion that $m+1=m$. It
follows that $h(j+1)=h(j)+1$ and hence  one obtains from ({\bf IV})
$$
f(j+1)=h(j)+j+1=h(j+1)+j =m+1.
$$
It follows that $f\big(f(m+1)\big)=m+1$.

\medskip
Case (ii).
Suppose $f(m+1)=h(m)+m+1$, so that $h(m+1)=h(m)+1$. Here put $j=h(m)+m$.
Thus $ j+1=h(m)+m+1=f(m+1)$, and using induction hypothesis one obtains
$$
h(j)=h\big(h(m)+m\big)=m+1.
$$
We show that $h(j+1)=h(j)$ in this case. Suppose the contrary that
$h(j+1)=h(j)+1$. Then ({\bf IV}) shows that
$$
f(j+1)=h(j)+j+1>h(j).
$$
The property of $f$ shows that (section {\bf 3}), $f(l)>h(j)$ for all
$l\geq j+1$. Since $f$ is surjective, it must be the case that
$$
h(j)\in \Big\{ f(1), f(2), \ldots, f(j)\Big\}.
$$
Thus $h(j)=f(r)$ for some $r\leq j$. If $m+1<r<j$, then $f(r)=h(j)=m+1
<r$. However $f(r)=h(r-1)$ or $h(r-1)+r$. The bound $f(r)<r$ implies
that $f(r)=h(r-1)$ which corresponds to $h(r)=h(r-1)$. Thus it follows
$h(r-1)=h(r)=f(r)=h(j)$, where $r-1<r<j$. However this contradicts the
property of $h$ that it does not assume the same value at three
integers. If $r=m+1$, then again $ h(j)=f(r)=f(m+1)=j+1$ contradicting
$h(j)\leq j$. If $r<m+1$, then $f(r)=h(j)=m+1$ and hence
$f(m+1)=f\big(f(r)\big)=r$ by induction hypothesis. This implies that
$f(m+1)=r\leq m$. However $f(m+1)=h(m)$ or $h(m)+m+1$. Using
$f(m+1)\leq m$, it may be concluded that $f(m+1)=h(m)$. But then
$h(m+1)=h(m)$, contradicting $h(m+1)=h(m)+1$. The only choice left is
$r=j$. Thus $h(j)=f(r)=f(j)$ and this gives
$$
f(j)=h(j)=h\big(h(m)+m\big) =m+1\leq j.
$$
Using $f(j)=h(j-1)$ or $h(j-1)+j$, it may be concluded that $f(j)=h(j-1)$.
Using ({\bf III}), $h(j)=h(j-1)=f(j)$ and
$$
f(j)=h(j-1) =h(j)=h\big(h(m)+m\big)=m+1.
$$
Using induction hypothesis,
$$
h\big(h(m-1)+m-1\big)=m.
$$
Comparing this with $h\big(h(m)+m-1\big)=h(j-1)=h(j)=m+1$, it follows that
$h(m)=h(m-1)+1$. Thus, we obtain
$$
f(m)=h(m-1)+m =h(m)-1+m =j-1.
$$
Using induction hypothesis, we also have $f\big(f(m)\big)=m$. Thus two
relations $f(j-1)=m$ and $f(j)=m+1$ are obtained. But 
 this is impossible since $f$ does not assume consecutive values at
 consecutive integers.  We conclude that $h(j+1)=h(j)$. In this case
$$
f(j+1)=h(j)=m+1,
$$
and hence $f\big(f(m+1)\big)=m+1$.

\medskip
{\bf Proof of} ({\bf c}):  
Here again there are two possibilities: $h(m+1)=h(m)$ or $h(m)+1$.

Case (i).
Suppose $h(m+1)=h(m)+1$. Then
\begin{eqnarray*}
h\big(h(m+1)+m+1\big) &=&h\big(h(m)+m+2\big)\\
&=&h\big(h(m)+m\big)+1 \text{~~{\em or}~~}h\big(h(m)+m\big)+2.
\end{eqnarray*}
Suppose $h\big(h(m)+m+2\big)=h\big(h(m)+m\big)+2$ holds. Then induction
hypothesis gives $h\big(h(m)+m\big) =m+1$ and
$$
h\big(h(m+1)+m+1\big) =h\big(h(m)+m\big)+2 =m+1+2=m+3.
$$
We observe that 
$$
h(m)+m\leq h(m)+m+1 \leq h(m+1)+m+1.
$$
Since $h$ is surjective, we conclude   $h\big(h(m)+m+1\big)=m+2$.

If
$h\big(h(m)+m\big)=h\big(h(m)+m-1\big)+1$, then $h\big(h(m)+m-1\big)=m$.
Moreover the condition $h\big(h(m)+m+1\big)=m+2=h\big(h(m)+m\big)+1$ implies
that $h\big(h(m)+m\big)$ lies in the set $\big\{ f(1), f(2), \ldots ,
f\big(h(m)+m\big)\big\}$. Thus $h\big(h(m)+m\big)=f(r)$ for some $r\leq
h(m)+m$. Therefore
$$
f(r)=h\big(h(m)+m\big) =m+1 =f\big(f(m+1)\big),$$
from ({\bf b)}. Since $f$ is one-one, it follows that $r=f(m+1)$. Thus the
bound $f(m+1)=r\leq h(m)+m$ is obtained. However $f(m+1)=h(m)$ or
$h(m)+m+1$. The
bound $f(m+1)\leq h(m)+m$ shows that $f(m+1)=h(m)$. But then
$h(m+1)=h(m)$ contradicting $h(m+1)=h(m)+1$. Thus the relation
$h\big(h(m)+m\big)=h\big(h(m)+m-1\big)$ must be true.

We have therefore $h\big(h(m)+m-1\big)=h\big(h(m)+m\big)=m+1$ and
$h\big(h(m-1)+m-1\big)=m$. Comparing these two, it may be concluded that
$h(m)=h(m-1)+1$. However this corresponds to $f(m)=h(m-1)+m$ and hence by
induction hypothesis
$$
m=f\big(f(m)\big) =f\big(h(m-1)+m\big).
$$
Now we have
$$
h\big(h(m-1)+m\big)=h\big(h(m)+m-1\big)=m+1.
$$
The properties ({\bf III}) and ({\bf IV})  show that
\begin{eqnarray*}
f\big(h(m-1)+m\big) &=&h\big(h(m-1)+m-1\big)\\
&&\text{{\em ~~or~~}}h\big(h(m-1)+m-1\big) +h(m-1)+m.
\end{eqnarray*}

If the first alternative holds, then
$h\big(h(m-1)+m\big)=h\big(h(m-1)+m-1\big)$ and hence
$$
m+1=h\big(h(m-1)+m\big)=h\big(h(m-1)+m-1\big)=m,
$$
where we have used induction hypothesis in the last equality. This absurdity
implies that the first alternative cannot be true. 

If the second alternative
holds, then again
$$
m=f\big(h(m-1)+m\big)
=h\big(h(m-1)+m-1\big) +h(m-1)+m>m,
$$
which is impossible. 

We may  thus  conclude that $h\big(h(m)+m+2\big)=h\big(h(m)+m\big)+2$ is not
valid. But then
$$
h\big(h(m)+m+2\big)=h\big(h(m)+m\big)+1= (m+1)+1=m+2.
$$

\medskip
Case (ii).
Suppose $h(m+1)=h(m)$. Then
$$
h\big(h(m+1)+m+1\big) =h\big(h(m)+m+1\big)
=h\big(h(m)+m\big) \text{~~or~~}h\big(h(m)+m\big)+1.
$$
In the first case
$$
f\big(h(m)+m+1\big)=h\big(h(m)+m\big)=m+1=f\big(f(m+1)\big),
$$
by ({\bf b}). Since $f$ is one-one, it follows that $f(m+1)=h(m)+m+1$. But
then $h(m+1)=h(m)+1$ contradicting $h(m+1)=h(m)$. Thus the second
alternative holds and we obtain
$$
h\big(h(m+1)+m+1\big)=h\big(h(m)+m+1\big)
=h\big(h(m)+m\big)+1 =m+2.
$$

This completes the proofs of ({\bf a)}, ({\bf b)} and ({\bf c)}. We
conclude that ({\bf V)}, ({\bf VI}) and ({\bf VII)} hold for all
values of $n$, thus completing the proof of Theorem \ref{thm:1}.

\section{Proof of Theorem 2} 

We prove several properties of the function $h$ satisfying the
equations (\ref{eq:eq1}), which are useful in the proof of Theorem
\ref{thm:1}.
First of all, it is necessary to check that the definition of $f$ makes
sense. In other words, it is part of the result that $h(n+1)=h(n)$ or
$h(n)+1$ and these are the only possibilities for the growth of $h$. This is
proved as a consequence of the relation (\ref{eq:eq1}).

\begin{lemma}
\label{lem:2}
Suppose $h: \N \to \N$ satisfies the functional equation {\em
(\ref{eq:eq1})}:
$$
h\big(h(n)\big)+h(n+1)=n+2.
$$
Then $h$ is a nondecreasing function on $\N$ and $h(n+1)=h(n)$ or
$h(n)+1$ for all $n\in{ \N}$.  Moreover $h(n)\leq n$ for all $n\in
\N$ and $h(n)\leq n-2$ for all $n\geq 6$.
\end{lemma}

\begin{pf}
We first show   that  $h(1)=1$, $h(2)=2$,
$h(3)=2$, $h(4)=3$, $h(5)=4$ and $h(6)=4$. Putting $n=1$ in
(\ref{eq:eq1}), we obtain
$$
h\big(h(1)\big)+h(2)=3.
$$
Since all the numbers involved are natural numbers, $h(2)\leq 2$. Thus
$h(2)=1$ or 2. Suppose $h(2)=1$. Taking $h(1)=k$, the above relation gives
$h(k)=2$. Taking $n=2$ in (\ref{eq:eq1}), we also get
$$
h\big(h(2)\big)+h(3)=4.
$$
Thus $h(3)=4-h(1)=4-k$. Since $h(3)\geq 1$, it follows that $k\leq 3$. Thus
$k=1$, 2 or 3. If $k=1$, then
$$
2=h\big(h(1)\big)=h(k)=h(1)=k=1,
$$
a contradiction. If $k=2$, then again
$$
2=h\big(h(1)\big)=h(k)=h(2)=1,
$$
giving a contradiction. Finally $k=3$ gives
$$
2=h\big(h(1)\big)=h(k) =h(3)=4-k=4-3=1,
$$
which again is absurd. Thus $h(2)=1$ is not feasible. It follows $h(2)=2$
and $h(k)=1$. Now taking $n=2$ in (\ref{eq:eq1}), we obtain
$$
h\big(h(2)\big)+h(3)=4.
$$
This leads to
$$
h(3)=4-h\big(h(2)\big)=4-h(2)=4-2=2.
$$
Recursively, we get
\begin{eqnarray*}
h(4)&=& 5-h\big(h(3)\big)=5-h(2)=5-2=3,\\
h(5)&=&6-h\big(h(4)\big)=6-h(3)=6-2=4,\\
h(6)&=&7-h\big(h(5)\big)=7-h(4)=7-3=4.
\end{eqnarray*}
Now an easy induction shows that $h(n)\geq 2$ for all $n\geq 2$. Suppose
$h(1)=k\geq 2$. Then
$$
3=h\big(h(1)\big)+h(2)=h(k)+h(2)\geq 2+2 =4,
$$
which is impossible. Thus $h(1)=1$  and the the first few values of $h$ are
obtained.

The values of $h(n)$ for $n=1,2,3$ show that
\begin{eqnarray*}
h(2)&=&2=h(1)+1,\\
h(3)&=& 2 =h(2).
\end{eqnarray*}
Suppose $h(j)=h(j-1)$ or $h(j-1)+1$ for all $j\leq n$. Now (\ref{eq:eq1})
gives
\begin{eqnarray*}
h\big(h(n)\big)+h(n+1)&=& n+2,\\
h\big(h(n-1)\big)+h(n)&=& n+1.
\end{eqnarray*}
Subtraction gives
$$
h\big(h(n)\big)-h\big(h(n-1)\big)+h(n+1)-h(n) =1.
$$
If $h(n)=h(n-1)$, then the above relation gives $h(n+1)-h(n)=1$. If
$h(n)=h(n-1)+1$, then
$$
h\big(h(n)\big)=h\big(h(n-1)+1\big)
=h\big(h(n-1)\big) \text{~~{\em or}~~} h\big(h(n-1)\big) +1,
$$
since $h(n-1)\leq n-1$ and the  induction hypothesis is applicable. In the first
case, $h(n+1)=h(n)+1$; in the second case, $h(n+1)=h(n)$. Thus it follows
that $h(n+1)=h(n)$ or $h(n)+1$. Hence $h$ increases in steps of 0 or 1.

It also follows that $h(j)\leq h(k)$ for $j\leq k$. Moreover the proof also
reveals that whenever $h(n)=h(n-1)+1$ and
$h\big(h(n-1)+1\big)=h\big(h(n-1)\big)+1$, then $h(n+1)=h(n)$.

Equation (\ref{eq:eq1}) shows that $h(n+1)\leq n+1$. Since $h(1)=1$, it
follows that $h(n)\leq n$ for all $n$. If $n\geq  6$, then $h(n)\geq
h(6)=4$. This implies that  $h\big(h(n)\big) \geq h(4)=3$. Thus
$$
h(n+1)=n+2-h\big(h(n)\big) \leq n+2-3 =n-1,
$$
for all $n\geq 6$. Since $h(6)=4$, it follows that $h(n)\leq n-2$ for all
$n\geq 6$.
\end{pf}

\begin{lemma}
\label{lem:3}
Let $h$ be a function satisfying the equation {\em (\ref{eq:eq1})}. Then
$h$ cannot take the same value at three consecutive
integers. Moreover, $h$ cannot take four distinct  values at four consecutive 
integers.
\end{lemma}
\begin{pf}
Suppose, if possible, $h(n)=h(n+1)=h(n+2)$, for some $n$. Now
(\ref{eq:eq1}) gives 
\begin{eqnarray*}
h\big(h(n)\big)+h(n+1)&=&n+2,\\
h\big(h(n+1)\big)+h(n+2)&=&n+3.
\end{eqnarray*}
Using $h(n+2)=h(n+1)$, the above relations give
$h\big(h(n+1)\big)=h\big(h(n)\big)+1$. However $h(n+1)=h(n)$ forces
$h\big(h(n+1)\big)=h\big(h(n)\big)$. These two are incompatible and hence
$h(n)=h(n+1)=h(n+2)$ cannot happen.

Suppose $h$ assumes four distinct values at four consecutive integers.
Since $h$ increases in steps of 0 or 1, we may assume 
say $h(n+1)=h(n)+1$, $h(n+2)=h(n+1)+1=h(n)+2$, and
$h(n+3)=h(n+2)+1=h(n)+3$. Using (\ref{eq:eq1}),
\begin{eqnarray*}
h\big(h(n)\big)+h(n+1)&=&n+2,\\
h\big(h(n+1)\big)+h(n+2)&=&n+3,\\
h\big(h(n+2)\big)+h(n+3)&=&n+4.
\end{eqnarray*}
It follows that
$$
h\big(h(n)\big)=h\big(h(n+1)\big)=h\big(h(n+2)\big),
$$
which reduces to
$$
h\big(h(n)\big)=h\big(h(n)+1\big)=h\big(h(n)+2\big).
$$
But this contradicts the property of $h$ that it cannot assume the
same value at three consecutive integers. Thus it follows that $h$
cannot take four distinct values at four consecutive integers.
\end{pf}

\begin{lemma}
\label{lem:4}
For each $n\in \N$,
$$ 
h(n)=\frac{\big(f(1)+f(2)+\cdots +f(n)\big)}{n}.
$$
Thus the sum $f(1)+f(2)+\cdots +f(n)$ is divisible by $n$, for each
$n\in \N$.
\end{lemma}
\begin{pf}
We use induction on $n$. For $n=1,2$, this may be verified using $h(1)=1$,
$h(2)=2$, $f(1)=1$ and $f(2)=3$. Suppose the relation holds for all $j\leq
n$. If $h(n+1)=h(n)$, then $f(n+1)=h(n)$ and hence
$$
\frac{f(1)+f(2)+\cdots +f(n)+f(n+1)}{n+1}
= \frac{nh(n)+h(n)}{n+1}=h(n)=h(n+1).
$$
If, on the other hand, $h(n+1)=h(n)+1$, then $f(n+1)=h(n)+n+1$ and hence
$$
\frac{f(1)+f(2)+\cdots +f(n)+f(n+1)}{n+1}
= \frac{nh(n)+h(n)+n+1}{n+1}
=h(n)+1=h(n+1).
$$
This proves inductive step and hence proves the assertion.
\end{pf}

\begin{lemma}
\label{lem:5}
The function $h$, satisfying the equation {\em (\ref{eq:eq1})} further
satisfies the relation
$$
h\big(h(n)+n\big)=n+1,
$$
for all $n\in {\N}$.
\end{lemma}
\begin{pf}
For $n=1,2$ this may be verified using the values  $h(1)=1$ and $h(2)=2$.
Suppose it holds for all $j\leq n$; i.e., $h\big(h(j)+j\big)=j+1$, for all
$j\leq n$. Consider $h\big(h(n+1)+n+1\big)$. If $h(n+1)=h(n)$, then
$$
h\big(h(n+1)+n+1\big) = h\big(h(n)+n+1\big)
= h\big(h(n)+n\big) \text{~~{\em or}~~} h\big(h(n)+n\big)+1.
$$

Suppose $h\big(h(n)+n+1\big)=h\big(h(n)+n\big)$. Then replacing $n$ in
(\ref{eq:eq1}) by $h(n)+n$, it takes the form
$$
h\Big(h\big(h(n)+n\big)\Big) +h\Big(h(n)+n+1\Big) =h(n)+n+2.
$$
If we use induction hypothesis, it reduces to
$$
h\big(n+1\big) +h\big(h(n)+n\big)=h(n)+n+2,
$$
or to $h(n+1)=h(n)+1$. This contradicts $h(n+1)=h(n)$. We conclude that
$h\big(h(n)+n+1\big)=h\big(h(n)+n\big)+1$. Thus
$$
h\big(h(n+1)+n+1\big)=h\big(h(n)+n\big)+1 =(n+1)+1=n+2.
$$

Suppose on the other hand $h(n+1)=h(n)+1$. In this case
$$
h\big(h(n+1)+n+1\big) = h\big(h(n)+n+2\big)
= h\big(h(n)+n\big)+1 \text{~~{\em or}~~} h\big(h(n)+n\big)+2.
$$
If $h\big(h(n)+n+2\big)=h\big(h(n)+n\big)+2$, then this implies that
$h\big(h(n)+n+2\big)=h\big(h(n)+n+1\big)+1$ and
$h\big(h(n)+n+1\big)=h\big(h(n)+n\big)+1$, because $h$ increases in
steps of 0 or 1. Using (\ref{eq:eq1}),
$$
h\Big(h\big(h(n)+n+1\big)\Big) +h\Big(h(n)+n+2\Big) =h(n)+n+3.
$$
This may be written in the form
$$
h\Big(h\big(h(n)+n\big)+1\Big) +h\Big(h(n)+n\Big)+2 =h(n)+n+3.
$$
The induction hypothesis reduces it to
$$
h(n+2)+n+3=h(n)+n+3.
$$
Thus $h(n+2)=h(n)$. This forces $h(n+2)=h(n+1)=h(n)$, contradicting
Lemma \ref{lem:3}. We conclude that $h\big(h(n)+n+2\big)=h\big(h(n)+n\big)+1$. But then
$$
h\big(h(n+1)+n+1\big) =h\big(h(n)+n+2\big)
=h\big(h(n)+n\big)+1=(n+1)+1 =n+2.
$$
This proves the result for $j=n+1$ and completes the induction. 
\end{pf}


We now complete the proof of Theorem \ref{thm:2}.  We show that  $f$
is, in fact,  an involution on $\N$,
i.e., $f\big(f(n)\big)=n$, for each $n$.

{\bf Proof of Theorem 2.}
Since $f(1)=1$,
$f(2)=3$ and $f(3)=2$, the result is true for $n=1,2,3$. Suppose $n>3$
and $f\big(f(j)\big)=j$, for all $j\leq n$. We show that
$f\big(f(n+1)\big)=n+1$. We consider two cases: $h(n+1)=h(n)$ and
$h(n+1)=h(n)+1$.

Case 1. Suppose $h(n+1)=h(n)$. Then $f(n+1)=h(n)$. Put
$j=h(n)-1$, and observe that $j>0$ since $n>3$. Since $h(n+1)=h(n)$,
Lemma \ref{lem:3}  shows that $h(n)=h(n-1)+1$. Hence $j=h(n)-1=h(n-1)$, and
$j+1=h(n)=f(n+1)$. Observe that
\begin{eqnarray*}
h(j+1)+j&=& h\big(h(n)\big)+h(n)-1\\
&=&h\big(h(n)\big)+h(n+1)-1\\
&=&(n+2)-1=n+1.
\end{eqnarray*}
We show that $h(j+1)=h(j)+1$. Suppose the contrary that $h(j+1)=h(j)$. Then
$h(j)+j=h(j+1)+j=n+1$. Thus
$$
n+1= h(j)+j=h\big(h(n-1)\big)+h(n)-1=(n+1)-1=n,
$$
which is absurd. It follows that $h(j+1)=h(j)+1$ and hence
$$
f(j+1)=h(j)+j+1=h(j+1)+j=n+1.
$$
Thus we obtain $f\big(f(n+1)\big)=n+1$.

\medskip Case 2. Suppose on the other hand $h(n+1)=h(n)+1$ and hence
$f(n+1)=h(n)+n+1$. Put $j=h(n)+n$. Then $ h(j)=h\big(h(n)+n\big)=n+1$,
by Lemma \ref{lem:5} and $j+1=h(n)+n+1 =f(n+1)$. We show that
$h(j+1)=h(j)$ in this case. If not, we must have  $h(j+1)=h(j)+1$ and hence
$$
h\big(h(n)+n+1\big)=h\big(h(n)+n\big)+1 =n+2.
$$
Now (\ref{eq:eq1}) gives
$$
h\Big(h\big(h(n)+n\big)\Big) +h\Big(h(n)+n+1\Big) =h(n)+n+2.
$$
This reduces to
$$
h(n+1)+n+2=h(n)+n+2.
$$
Thus $h(n+1)=h(n)$, contradicting $h(n+1)=h(n)+1$.  It follows that
$h(j+1)=h(j)$ and using the definition of $f$, we obtain
$$
f(j+1)=h(j)=n+1.
$$
We obtain $f\big(f(n+1)\big)=n+1$.

Thus we see that $f\big(f(n)\big)=n$ for all $n\in \N$. This implies
that $f$ is  a bijection on $\N$. Lemma \ref{lem:4} shows that $n$
divides $f(1)+f(2)+\cdots +f(n)$ for all $n\in \N$. 

\section{Acknowledgements} 

The author thanks referee for invaluable
comments which helped in improving the presentation of the results in
the paper.
\begin{thebibliography}{9}

\bibitem{ShQ96}
A. Shapovalov, Problem M 185, {\em Quantum\/}, {\bf 7} (1),
(September/October 1996), pp.\ 22, 59.

\bibitem{BjvFeq02}
B. J. Venkatachala, {\em Functional Equations, A Problem Solving
Approach}, Prism Books Pvt. Ltd., Bangalore, India, 2002.

\bibitem{Sloane} N. J. A. Sloane,
\href{http://www.research.att.com/~njas/sequences/}{The On-Line
Encylopedia of Integer Sequences}.
\end{thebibliography}



\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11B13.

\noindent \emph{Keywords: } Shapovalov, curious bijection, greedy algorithm. 

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A019444}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 16 2009;
revised version received  November 11 2009.
Published in {\it Journal of Integer Sequences}, November 16 2009.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

\hrule
\bigskip



\end{document}