A Curious Bijection on Natural Numbers

B. J. Venkatachala MO Cell, HBCSE(TIFR) Department of Mathematics Indian Institute of Science Bangalore-560012 India

                    jana@math.iisc.ernet.in

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 involution on the set of all natural numbers.

1 Introduction

The following problem was posed by A. Shapovalov [1]:

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, …?

The published solution, though ingenious, is not intuitive. Shapovalov inductively defines a sequence ⟨a_{n}⟩, which appears as a sequence \underline{A019444} in Sloane’s Encyclopedia of Integer Sequences [3], as follows. Put a_{1} = 1 and having defined a_{1}, a_{2}, …, a_{k}, first compute n_{k} = (a_{1} + a_{2} + ⋯ + a_{k})/k. Now define

a_{k+1} = \begin{cases}n_{k}, & if n_{k} is not already in the set \{a_{1}, a_{2}, …, a_{k}\}; \\ n_{k} + k + 1, & if n_{k} is in the set \{a_{1}, a_{2}, …, a_{k}\}. \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} + ⋯ + 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 ℕ, the set of all natural numbers, such that n divides f(1) + f(2) + ⋯ + f(n) for each n. A natural approach is the so called the greedy algorithm. One can start with f(1) = 1 and having defined f(j) for 1 ≤ j ≤ n, the choice for f(n + 1) is the least positive integer l, not in the set {f(1), f(2), …, f(n)}, such that (n + 1) divides f(1) + f(2) + ⋯ + 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 {f(1), f(2)}, 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 {f(1), f(2), f(3)}. However if we add 4 more, then 8 + 4 = 12 is also divisible by 4 and 2 + 4 = 6 is not in the set {f(1), f(2), f(3)}. 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 greedy algorithm works and the nature of f(n) for

small n. The table also includes the average function h(n) = \frac{f(1) + f(2) + ⋯ + f(n)}{n}.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\ f(n) & 1 & 3 & 2 & 6 & 8 & 4 & 11 & 5 & 14 & 16 & 7 & 19 & 21 & 9 & 24 & 10 & 27 & 29 & 12 \\ h(n) & 1 & 2 & 2 & 3 & 4 & 4 & 5 & 5 & 6 & 7 & 7 & 8 & 9 & 9 & 10 & 10 & 11 & 12 & 12 \end{matrix}

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.

Lemma 1. Let f and h be functions defined on ℕ as above. Then

(I) h is a nondecreasing function on ℕ and h(n) ≤ n;

(II) h(n + 1) = h(n) or h(n) + 1, for all n ∈ ℕ;

(III) h(n + 1) = h(n) ⟺ f(n + 1) = h(n), for all n ∈ ℕ;

(IV) h(n + 1) = h(n) + 1 ⟺ f(n + 1) = h(n) + n + 1, for all n ∈ ℕ.

Much deeper properties of the functions f and h are given by Theorem 1.

Theorem 1. The functions f and h also satisfy, for all n ∈ ℕ,

(V) h(h(n)) + h(n + 1) = n + 2;

(VI) f(f(n)) = n;

(VII) h(h(n) + n) = n + 1.

A close look at this way of defining f and Shapovalov’s sequence ⟨a_{n}⟩ 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 ≤ 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 (V), (VI) and (VII). In particular the property (VI) shows that f is indeed a bijection. We prove all these in the sequel.

The involutive property of f is mentioned in [3]. 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 1, is it possible to single out a particular property which tells about the remaining ones? It turns out that (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(h(n)) + h(n + 1) = n + 2,

for all n ∈ ℕ, uniquely determines the function h. The surprising fact is that this function is related to the Golden Ratio α, given by α = (1 + \sqrt{5})/2. In fact, one can show that h(n) = ⌊nα⌋ − n + 1, where ⌊x⌋ denotes the greatest integer not exceeding x; [2]. 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.

Theorem 2. Suppose h : ℕ → ℕ is a function such that

h(h(n)) + h(n + 1) = n + 2,  (1)

holds for all n ∈ ℕ. Define f : ℕ → ℕ by f(1) = 1 and

f(n + 1) = \begin{cases}h(n), & if h(n + 1) = h(n); \\ h(n) + n + 1, & if h(n + 1) = h(n) + 1. \end{cases}

Then f is a bijection on ℕ such that for each n ∈ ℕ, the sum f(1) + f(2) + ⋯ + f(n) is divisible by n.

Thus the functional equation (1) on ℕ uniquely determines a function h on ℕ and this leads to a bijection f on ℕ such that for every natural number n the sum f(1) + f(2) + ⋯ + f(n) is divisible by n, which was sought by Shapovalov.

2 Proof of Lemma 1

We prove some simple properties of f and h in this section, as stated in Lemma 1. Proof. 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 ≤ j ≤ n. Thus we have h(j) ≤ j, for 1 ≤ j ≤ n; h(j + 1) = h(j) or h(j) + 1, for 1 ≤ j ≤ n − 1. This in particular implies that h(1) ≤ h(2) ≤ ⋯ ≤ h(n). Moreover f(j + 1) = h(j) ⟺ h(j + 1) = h(j), for 1 ≤ j ≤ n − 1 and f(j + 1) = h(j) + j + 1 ⟺ h(j + 1) = h(j) + 1, for 1 ≤ j ≤ n − 1. Let l be the least positive integer such that (n + 1) divides f(1) + f(2) + ⋯ + f(n) + l. Thus

(n + 1)k = f(1) + f(2) + ⋯ + 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 ≤ 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 ≥ n + 1 contradicting the induction hypothesis h(n) ≤ n. We conclude that l = h(n). In other words, the least positive integer l such that (n + 1) divides f(1) + f(2) + ⋯ + f(n) + l is equal to h(n), the average of f(1) + f(2) + ⋯ + f(n).

If h(n) does not belong to the set {f(1), f(2), …, f(n)}, 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 {f(1), f(2), …, f(n)}, then we consider h(n) + n + 1. Obviously f(1) + f(2) + ⋯ + 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 {f(1), f(2), …, f(n)}. Suppose to the contrary that h(n) + n + 1 lies in the set {f(1), f(2), …, f(n)}. Then h(n) + n + 1 = f(j) for some j ≤ 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) ≤ 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) ≤ h(n) by induction hypothesis. Thus h(n) + n + 1 is not an element of {f(1), f(2), …, f(n)}. It follows that h(n) + n + 1 is the least positive integer l not in the set {f(1), f(2), …, f(n)} such that (n + 1) divides f(1) + f(2) + ⋯ + 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) + ⋯ + 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) ≤ h(n + 1) and h(n + 1) ≤ n + 1. This proves inductive step and the properties (I)-(IV) are true for all values of n. □

3 Some more consequences

Here are some more consequences of the definition and the properties proved in Lemma 1. These ar useful in completing the proof of Theorem 1.

• 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 ≥ 1. Since h is a nondecreasing function of n, we have h(n) ≤ h(n + 1) ≤ 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 {f(1), f(2), …, f(n), f(n + 1)}, 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 {f(1), f(2), …, f(n), f(n + 1)}. (In fact equal to f(n + 1).) This contradiction proves the statement.

• 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 ≥ 1.

• The function f is surjective.

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

• The function f is one-one.

Suppose f(m) = f(k) for some m < k. The property (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 {f(1), f(2), …, f(m)} which itself is a subset of {f(1), f(2), …, f(k − 1)}, as m ≤ 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) ≤ 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) ≤ h(k − 1). Thus f(m) ≠ f(k) if m ≠ k.

• The inequality h(n) ≤ n − 2 holds for all n ≥ 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.

• If f(n + 1) > h(n), then f(j) > h(n) for all j ≥ n + 1.

In fact

f(n + 2) ≥ h(n + 1) = \frac{f(1) + f(2) + ⋯ + f(n + 1)}{n + 1}
= \frac{nh(n) + f(n + 1)}{n + 1}
> h(n).

An easy induction proves that f(j) > h(n) for all j ≥ n + 1.

• There are no integers k ≥ 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 ≥ 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

kh(k) = f(1) + f(2) + ⋯ + f(k)
= f(1) + f(2) + ⋯ + f(k − 2) + 2f(k − 1) + 1
= (k − 2)h(k − 2) + 2f(k − 1) + 1.

This implies that

k(h(k) − h(k − 2)) = −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

k = −2h(k − 2) + 2f(k − 1) + 1
= 2(f(k − 1) − h(k − 2)) + 1.

But f(k − 1) = h(k − 2) or h(k − 2) + k − 1. In both the cases k = 1 contradicting k > 2.

4 Proof of Theorem 1

We prove the deeper properties of h and f as stated in Theorem 1. The following properties hold for all values of n ∈ ℕ:

(V) h(h(n)) + h(n + 1) = n + 2;

(VI) f(f(n)) = n;

(VII) h(h(n) + n) = n + 1.

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(h(n)) + h(n + 1) = h(h(1)) + h(2) = h(1) + h(2) = 3 = n + 2;
f(f(n)) = f(f(1)) = f(1) = 1 = n;
h(h(n) + n) = h(h(1) + 1) = h(2) = 2 = n + 1.

These may also be verified for n = 2, 3, 4, 5, 6. So we assume that m > 6 and (V)-(VII) are true for all n ≤ m. We prove them for n = m + 1. We have to prove three statements:

(a) h(h(m + 1)) + h(m + 2) = m + 3;

(b) f(f(m + 1)) = m + 1;

(c) h(h(m + 1) + m + 1) = m + 2.

Proof of (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

h(h(m + 1)) + h(m + 2) = h(h(m)) + h(m + 1) + 1
= (m + 2) + 1 = m + 3.

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(h(m)+1) = h(h(m)) or h(h(m)+1) = h(h(m))+1. If h(h(m)+1) = h(h(m)), then it must be the case that h(h(m) + 2) = h(h(m) + 1) + 1; otherwise h assumes the same value at three consecutive integers h(m), h(m) + 1 and h(m) + 2. Thus using the property (IV), we obtain

f(h(m) + 2) = h(h(m) + 1) + h(m) + 2
= h(h(m) + 1) + h(m + 1) + 1
= h(h(m)) + h(m + 1) + 1
= (m + 2) + 1
= m + 3,

where induction hypothesis is invoked. But h(m) + 2 ≤ m for m ≥ 6. Again by induction hypothesis, we get

f(f(h(m) + 2)) = h(m) + 2.

It follows that

f(m + 3) = h(m) + 2
= h(m + 1) + 1 = h(m + 2) + 1.

But this is impossible, since either f(m + 3) = h(m + 2) or h(m + 2) + m + 3. We conclude that h(h(m) + 1) = h(h(m)) is not possible.

Thus we must have h(h(m) + 1) = h(h(m)) + 1. In this case

h(h(m + 1)) + h(m + 2) = h(h(m) + 1) + h(m + 1)
= h(h(m)) + 1 + h(m + 1)
= (m + 2) + 1 = m + 3,

where again induction hypothesis that h(h(m)) + 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(h(m) + 1) = h(h(m)) or h(h(m) + 1) = h(h(m)) + 1.

If h(h(m) + 1) = h(h(m)) holds, we have

h(h(m + 1)) + h(m + 2) = h(h(m) + 1) + h(m + 1) + 1
= h(h(m)) + h(m + 1) + 1
= (m + 2) + 1 = m + 3,

using h(h(m)) + h(m + 1) = m + 2.

If on the other hand h(h(m) + 1) = h(h(m)) + 1, then the property (IV) shows that

f(h(m) + 1) = h(h(m)) + h(m) + 1
= h(h(m)) + h(m + 1)
= m + 2.

Since h(m + 1) ≤ m, induction hypothesis gives

h(m + 1) = f(f(h(m + 1))) = f(m + 2).

But then (III) implies that h(m + 2) = h(m + 1) contradicting h(m + 2) = h(m + 1) + 1. Thus the case h(h(m) + 1) = h(h(m)) + 1 cannot occur when h(m + 1) = h(m) + 1 and h(m + 2) = h(m + 1) + 1.

This completes the proof of (V) for n = m + 1.

Proof of (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 (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

h(j + 1) + j = h(h(m)) + h(m) − 1
= h(h(m)) + h(m + 1) − 1
= m + 1;

we have used induction hypothesis that h(h(m)) + 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(h(m) − 1) + h(m) − 1 = m + 1.

Now h(m) − 1 = h(m − 1) and hence

h(h(m) − 1) + h(m) − 1 = h(h(m − 1)) + 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 (IV)

f(j + 1) = h(j) + j + 1 = h(j + 1) + j = m + 1.

It follows that f(f(m + 1)) = m + 1.

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(h(m) + m) = m + 1.

We show that h(j + 1) = h(j) in this case. Suppose the contrary that h(j + 1) = h(j) + 1. Then (IV) shows that

f(j + 1) = h(j) + j + 1 > h(j).

The property of f shows that (section 3), f(l) > h(j) for all l ≥ j + 1. Since f is surjective, it must be the case that

h(j) ∈ {f(1), f(2), …, f(j)}.

Thus h(j) = f(r) for some r ≤ 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) ≤ j. If r < m + 1, then f(r) = h(j) = m + 1 and hence f(m + 1) = f(f(r)) = r by induction hypothesis. This implies that f(m + 1) = r ≤ m. However f(m + 1) = h(m) or h(m) + m + 1. Using f(m + 1) ≤ 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(h(m) + m) = m + 1 ≤ j.

Using f(j) = h(j − 1) or h(j − 1) + j, it may be concluded that f(j) = h(j − 1). Using (III), h(j) = h(j − 1) = f(j) and

f(j) = h(j − 1) = h(j) = h(h(m) + m) = m + 1.

Using induction hypothesis,

h(h(m − 1) + m − 1) = m.

Comparing this with h(h(m) + m − 1) = 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(f(m)) = 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(f(m + 1)) = m + 1.

Proof of (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

h(h(m + 1) + m + 1) = h(h(m) + m + 2)
= h(h(m) + m) + 1 or h(h(m) + m) + 2.

Suppose h(h(m) + m + 2) = h(h(m) + m) + 2 holds. Then induction hypothesis gives h(h(m) + m) = m + 1 and

h(h(m + 1) + m + 1) = h(h(m) + m) + 2 = m + 1 + 2 = m + 3.

We observe that

h(m) + m ≤ h(m) + m + 1 ≤ h(m + 1) + m + 1.

Since h is surjective, we conclude h(h(m) + m + 1) = m + 2.

If h(h(m) + m) = h(h(m) + m − 1) + 1, then h(h(m) + m − 1) = m. Moreover the condition h(h(m) + m + 1) = m + 2 = h(h(m) + m) + 1 implies that h(h(m) + m) lies in the set {f(1), f(2), …, f(h(m) + m)}. Thus h(h(m) + m) = f(r) for some r ≤ h(m) + m. Therefore

f(r) = h(h(m) + m) = m + 1 = f(f(m + 1)),

from (b). Since f is one-one, it follows that r = f(m + 1). Thus the bound f(m + 1) = r ≤ h(m) + m is obtained. However f(m + 1) = h(m) or h(m) + m + 1. The bound f(m+1) ≤ 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(h(m) + m) = h(h(m) + m − 1) must be true.

We have therefore h(h(m) + m − 1) = h(h(m) + m) = m + 1 and h(h(m − 1) + m − 1) = 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(f(m)) = f(h(m − 1) + m).

Now we have

h(h(m − 1) + m) = h(h(m) + m − 1) = m + 1.

The properties (III) and (IV) show that

f(h(m − 1) + m) = h(h(m − 1) + m − 1)
or h(h(m − 1) + m − 1) + h(m − 1) + m.

If the first alternative holds, then h(h(m − 1) + m) = h(h(m − 1) + m − 1) and hence

m + 1 = h(h(m − 1) + m) = h(h(m − 1) + m − 1) = 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(h(m − 1) + m) = h(h(m − 1) + m − 1) + h(m − 1) + m > m,

which is impossible.

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

h(h(m) + m + 2) = h(h(m) + m) + 1 = (m + 1) + 1 = m + 2.

Case (ii). Suppose h(m + 1) = h(m). Then

h(h(m + 1) + m + 1) = h(h(m) + m + 1) = h(h(m) + m) or h(h(m) + m) + 1.

In the first case

f(h(m) + m + 1) = h(h(m) + m) = m + 1 = f(f(m + 1)),

by (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(h(m + 1) + m + 1) = h(h(m) + m + 1) = h(h(m) + m) + 1 = m + 2.

This completes the proofs of (a), (b) and (c). We conclude that (V), (VI) and (VII) hold for all values of n, thus completing the proof of Theorem 1.

5 Proof of Theorem 2

We prove several properties of the function h satisfying the equations (1), which are useful in the proof of Theorem 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 (1).

Lemma 2. Suppose h : ℕ → ℕ satisfies the functional equation (1):

h(h(n)) + h(n + 1) = n + 2.

Then h is a nondecreasing function on ℕ and h(n + 1) = h(n) or h(n) + 1 for all n ∈ ℕ. Moreover h(n) ≤ n for all n ∈ ℕ and h(n) ≤ n − 2 for all n ≥ 6.

Proof. 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 (1), we obtain

h(h(1)) + h(2) = 3.

Since all the numbers involved are natural numbers, h(2) ≤ 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 (1), we also get

h(h(2)) + h(3) = 4.

Thus h(3) = 4 − h(1) = 4 − k. Since h(3) ≥ 1, it follows that k ≤ 3. Thus k = 1, 2 or 3. If k = 1, then

2 = h(h(1)) = h(k) = h(1) = k = 1,

a contradiction. If k = 2, then again

2 = h(h(1)) = h(k) = h(2) = 1,

giving a contradiction. Finally k = 3 gives

2 = h(h(1)) = 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 (1), we obtain

h(h(2)) + h(3) = 4.

This leads to

h(3) = 4 − h(h(2)) = 4 − h(2) = 4 − 2 = 2.

Recursively, we get

h(4) = 5 − h(h(3)) = 5 − h(2) = 5 − 2 = 3,
h(5) = 6 − h(h(4)) = 6 − h(3) = 6 − 2 = 4,
h(6) = 7 − h(h(5)) = 7 − h(4) = 7 − 3 = 4.

Now an easy induction shows that h(n) ≥ 2 for all n ≥ 2. Suppose h(1) = k ≥ 2. Then

3 = h(h(1)) + h(2) = h(k) + h(2) ≥ 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

h(2) = 2 = h(1) + 1,
h(3) = 2 = h(2).

Suppose h(j) = h(j − 1) or h(j − 1) + 1 for all j ≤ n. Now (1) gives

h(h(n)) + h(n + 1) = n + 2,
h(h(n − 1)) + h(n) = n + 1.

Subtraction gives

h(h(n)) − h(h(n − 1)) + 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(h(n)) = h(h(n − 1) + 1) = h(h(n − 1)) or h(h(n − 1)) + 1,

since h(n−1) ≤ 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) ≤ h(k) for j ≤ k. Moreover the proof also reveals that whenever h(n) = h(n − 1) + 1 and h(h(n − 1) + 1) = h(h(n − 1)) + 1, then h(n + 1) = h(n).

Equation (1) shows that h(n + 1) ≤ n + 1. Since h(1) = 1, it follows that h(n) ≤ n for all n. If n ≥ 6, then h(n) ≥ h(6) = 4. This implies that h(h(n)) ≥ h(4) = 3. Thus

h(n + 1) = n + 2 − h(h(n)) ≤ n + 2 − 3 = n − 1,

for all n ≥ 6. Since h(6) = 4, it follows that h(n) ≤ n − 2 for all n ≥ 6. □

Lemma 3. Let h be a function satisfying the equation (1). Then h cannot take the same value at three consecutive integers. Moreover, h cannot take four distinct values at four consecutive integers.

Proof. Suppose, if possible, h(n) = h(n + 1) = h(n + 2), for some n. Now (1) gives

h(h(n)) + h(n + 1) = n + 2,
h(h(n + 1)) + h(n + 2) = n + 3.

Using h(n + 2) = h(n + 1), the above relations give h(h(n + 1)) = h(h(n)) + 1. However h(n + 1) = h(n) forces h(h(n + 1)) = h(h(n)). 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 (1),

h(h(n)) + h(n + 1) = n + 2,
h(h(n + 1)) + h(n + 2) = n + 3,
h(h(n + 2)) + h(n + 3) = n + 4.

It follows that

h(h(n)) = h(h(n + 1)) = h(h(n + 2)),

which reduces to

h(h(n)) = h(h(n) + 1) = h(h(n) + 2).

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

Lemma 4. For each n ∈ ℕ,

h(n) = \frac{(f(1) + f(2) + ⋯ + f(n))}{n}.

Thus the sum f(1) + f(2) + ⋯ + f(n) is divisible by n, for each n ∈ ℕ.

Proof. 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 ≤ n. If h(n + 1) = h(n), then f(n + 1) = h(n) and hence

\frac{f(1) + f(2) + ⋯ + 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) + ⋯ + 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. □

Lemma 5. The function h, satisfying the equation (1) further satisfies the relation

h(h(n) + n) = n + 1,

for all n ∈ ℕ.

Proof. For n = 1, 2 this may be verified using the values h(1) = 1 and h(2) = 2. Suppose it holds for all j ≤ n; i.e., h(h(j) + j) = j + 1, for all j ≤ n. Consider h(h(n + 1) + n + 1). If h(n + 1) = h(n), then

h(h(n + 1) + n + 1) = h(h(n) + n + 1) = h(h(n) + n) or h(h(n) + n) + 1.

Suppose h(h(n) + n + 1) = h(h(n) + n). Then replacing n in (1) by h(n) + n, it takes the form

h(h(h(n) + n)) + h(h(n) + n + 1) = h(n) + n + 2.

If we use induction hypothesis, it reduces to

h(n + 1) + h(h(n) + n) = h(n) + n + 2,

or to h(n+1) = h(n)+1. This contradicts h(n+1) = h(n). We conclude that h(h(n)+n+1) = h(h(n) + n) + 1. Thus

h(h(n + 1) + n + 1) = h(h(n) + n) + 1 = (n + 1) + 1 = n + 2.

Suppose on the other hand h(n + 1) = h(n) + 1. In this case

h(h(n + 1) + n + 1) = h(h(n) + n + 2) = h(h(n) + n) + 1 or h(h(n) + n) + 2.

If h(h(n)+n+2) = h(h(n)+n)+2, then this implies that h(h(n)+n+2) = h(h(n)+n+1)+1 and h(h(n) + n + 1) = h(h(n) + n) + 1, because h increases in steps of 0 or 1. Using (1),

h(h(h(n) + n + 1)) + h(h(n) + n + 2) = h(n) + n + 3.

This may be written in the form

h(h(h(n) + n) + 1) + h(h(n) + n) + 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 3. We conclude that h(h(n) + n + 2) = h(h(n) + n) + 1. But then

h(h(n + 1) + n + 1) = h(h(n) + n + 2) = h(h(n) + n) + 1 = (n + 1) + 1 = n + 2.

This proves the result for j = n + 1 and completes the induction. □

We now complete the proof of Theorem 2. We show that f is, in fact, an involution on ℕ, i.e., f(f(n)) = n, for each n.

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(f(j)) = j, for all j ≤ n. We show that f(f(n+1)) = 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 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

h(j + 1) + j = h(h(n)) + h(n) − 1
= h(h(n)) + h(n + 1) − 1
= (n + 2) − 1 = n + 1.

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(h(n − 1)) + 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(f(n + 1)) = n + 1.

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(h(n)+n) = n+1, by Lemma 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(h(n) + n + 1) = h(h(n) + n) + 1 = n + 2.

Now (1) gives

h(h(h(n) + n)) + h(h(n) + n + 1) = 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(f(n + 1)) = n + 1.

Thus we see that f(f(n)) = n for all n ∈ ℕ. This implies that f is a bijection on ℕ. Lemma 4 shows that n divides f(1) + f(2) + ⋯ + f(n) for all n ∈ ℕ.

6 Acknowledgements

The author thanks referee for invaluable comments which helped in improving the presentation of the results in the paper.

References

[1] A. Shapovalov, Problem M 185, Quantum, 7 (1), (September/October 1996), pp. 22, 59.

[2] B. J. Venkatachala, Functional Equations, A Problem Solving Approach, Prism Books Pvt. Ltd., Bangalore, India, 2002.

[3] N. J. A. Sloane, The On-Line Encylopedia of Integer Sequences.

2000 Mathematics Subject Classification: Primary 11B13. Keywords: Shapovalov, curious bijection, greedy algorithm.

(Concerned with sequence \underline{A019444}.)

Received revised version received Published in Journal of Integer Sequences,

Return to Journal of Integer Sequences home page.