Additive Functions on the Greedy and Lazy Fibonacci Expansions

Kalyan Chakraborty Harish-Chandra Research Institute Chhatnag Road, Jhunsi Allahabad, UP 211019 India

                   kalyan@hri.res.in

Imre Kátai and Bui Minh Phong Computer Algebra Department Eötvös Loránd University Pázmány Péter Sétány I/C 1117 Budapest Hungary

                   katai@inf.elte.hu
                    bui@inf.elte.hu

Abstract

We find all complex-valued functions that are additive with respect to both the greedy and the lazy Fibonacci expansions. We take it a little further by considering the subsets of these functions that are also multiplicative. In the final section we extend these ideas to Tribonacci expansions.

1 Introduction

The purpose of this paper is to study complex-valued functions that are additive with respect to (both greedy and lazy) Fibonacci and Tribonacci expansions. We begin by studying the functions with respect to Fibonacci expansions. The greedy Fibonacci expansion of a natural number was studied by Ostrowski [4], Zeckendorf [7], and Lekkerkerker [3], among many others. These days, authors call this greedy Fibonacci expansion the “Zeckendorf expansion”, but Ostrowski [4] introduced it much earlier and in a more general setup. In the later sections we study a subset of the above set of functions, which is also multiplicative in nature. The lazy and greedy Tribonacci expansion of a natural number are defined analogously, and in the final section we extend our study of these functions to the Tribonacci expansions. We refer to the work of Carlitz, Scoville, and Hoggatt [2] for generalizations of Fibonacci representations.

2 F-additive and F-lazy additive functions

2.1 Fibonacci sequence

Let, as usual, ℕ, ℝ, ℂ be the set of positive integers, real and complex numbers, respectively. Let ℕ_{0} = ℕ ∪ {0} be the set of non-negative integers and F = (F_{n})_{n≥0} be the sequence of Fibonacci numbers defined as follows:

F_{1} = 1, F_{2} = 2 and F_{m+2} = F_{m+1} + F_{m} (m ∈ ℕ).

Every natural number n has at least one expansion of the form

n = ∑_{ν=1}^{k} ϵ_{ν}F_{ν}  (1)

where the coefficients ϵ_{ν} ∈ {0, 1}. The expansion (1) is called the greedy or regular expansion of n and is characterized by the property that

ϵ_{l}ϵ_{l+1} = 0 (l = 1, …, k − 1).

Similarly, the lazy expansion

n = ∑_{μ=1}^{h} δ_{μ}F_{μ}, δ_{μ} ∈ {0, 1}, δ_{h} = 1  (2)

is characterized by the property that no two consecutive zeros are preceded by a one. Noting that 0F_{μ}+0F_{μ+1}+1F_{μ+2} can be replaced by 1F_{μ}+1F_{μ+1}+0F_{μ+2}. It is known that every such sequence is the lazy expansion of some integer (cf. Steiner [5, Lemma 1]). Let f : ℕ ⟶ ℂ be a function and we say that f is F-additive for the regular expansion (1) if

f(n) = ∑_{ν=1}^{k} ϵ_{ν}f(F_{ν}).

Let A_{F}^{(1)} be the set of such F-additive functions. If g : ℕ ⟶ ℂ is such that

g(n) = ∑_{μ=1}^{h} δ_{μ}g(F_{μ})

with expansion of n as in (2), then we say that g is F-lazy additive. We denote the set of these functions by A_{F}^{(2)} and set B = A_{F}^{(1)} ∩ A_{F}^{(2)}. Remark 1. We denote an element of B by f for notational convenience even though we have already written f ∈ A_{F}^{(1)}.

Theorem 2. Let α = \frac{1+\sqrt{5}}{2} and β = \frac{1−\sqrt{5}}{2}. If f ∈ B, then

f(F_{m}) = d_{1}α^{m} + d_{2}β^{m}, (m = 1, 2, …)  (3)

where d_{i}(i = 1, 2) are constants.

Conversely, if (3) holds, then f ∈ B. Also for an arbitrary expansion

n = ∑_{ν=1}^{k} e_{ν}F_{ν}, e_{ν} ∈ {0, 1},

one has

f(n) = ∑_{ν=1}^{k} e_{ν}f(F_{ν}).

Proof. Let us assume that f ∈ B and x_{k} = f(F_{k}). The lazy expansions of F_{i}(i = 1, 2, 3) are

F_{i} = F_{i}(i = 1, 2) and F_{3} = F_{1} + F_{2}.

Let k ≥ 4 and that S_{k} = ∑_{n=1}^{k} F_{n}. Now it is easy to see

F_{k+2} = S_{k} + 2 (k = 1, 2, …).

Thus the largest component in the lazy expansion of F_{k+2} is F_{k+1}. Hence:

(lazy expansion of F_{k+2}) = F_{k+1} + (lazy expansion of F_{k}) k ≥ 4.

Thus,

x_{k+2} = x_{k+1} + x_{k} (k = 1, 2, …).  (4)

Let us consider a sequence {x_{k}}_{k≥1} so that (4) holds for its terms. Let

n = e_{1}F_{1} + ⋯ + e_{k}F_{k}, n ≥ 3, e_{i} ∈ {0, 1}  (5)

and

σ (n|e_{1}, …, e_{k}) = ∑_{ν=1}^{k} e_{ν}x_{ν}.  (6)

We shall prove that σ (as defined in (6)) does not depend on e_{1}, …, e_{k}. This can be verified directly for small values of n (e.g., up to n = 6), but for large n we can proceed as follows. Let us consider the largest ν, if there is any, for which e_{ν} = e_{ν+1} = 1. In such a situation we change

1F_{ν} + 1F_{ν+1} → 1F_{ν+2}

in the representation (5). In the case when ν = k − 1, we have

n = e_{1}F_{1} + ⋯ + e_{k−2}F_{k−2} + 0F_{k−1} + 0F_{k−2} + 1F_{k+1}
= ∑_{ν=1}^{k+1} e′_{ν}x_{ν}.

In case when ν < k − 1 it is clear that e_{ν+2} = 0. After these substitutions we get

n = ∑_{ν=1}^{k} e′_{ν}F_{ν}

with e′_{h} = e_{h} if h ≠ ν, ν + 1, ν + 2. Also e′_{ν} = e′_{ν+1} = 0 and e′_{ν+2} = 1.

Thus in both the cases

σ (n|e′_{1}, …, e′_{k}) or σ (n|e′_{1}, …, e′_{k+1}) = σ (n|e_{1}, …, e_{k}) .

On repeating this algorithm, after some steps we arrive at the greedy expansion. This completes the proof of Theorem 2.

2.2 Modified Fibonacci sequence

Let F^{∗} = (F_{n}^{∗})_{n≥0} be the modified Fibonacci sequence defined as follows:

F_{0}^{∗} = 0, F_{1}^{∗} = 1 and F_{m+2}^{∗} = F_{m+1}^{∗} + F_{m}^{∗} (m = 0, 1, …).

Then

F_{m+1}^{∗} = F_{m} (m = 1, 2, …).

The greedy and lazy expansions of positive integers can be defined analogously and Theorem 2 remains true with the condition that f(F_{1}^{∗}) = f(F_{2}^{∗}). We give an outline of the proof for the sake of completeness.

Theorem 3. Let f be F^{∗}-greedy and F^{∗}-lazy additive. Then

f(n) = cn (n ∈ ℕ_{0})

where c is an arbitrary constant.

Proof. We have as before f(F_{m}^{∗}) = d_{1}α^{m} + d_{2}β^{m}. Taking into account that f(F_{1}^{∗}) = f(F_{2}^{∗}), we have

d_{1}α + d_{2}β = d_{1}α^{2} + d_{2}β^{2},

and thus

d_{1}α(α − 1) = −d_{2}β(β − 1).

Clearly α(α − 1) = β(β − 1) = 1 and this holds if and only if d_{2} = −d_{1}. Also using Binet’s formula [6] we have

F_{m}^{∗} = \frac{1}{\sqrt{5}}α^{m} − \frac{1}{\sqrt{5}}β^{m} for m ∈ ℕ.

Hence we obtain that

f(F_{m}^{∗}) = (d_{1}\sqrt{5})F_{m}^{∗} and f(n) = (d_{1}\sqrt{5})n.

Theorem 3 is now true with c = d_{1}\sqrt{5}.

Remark 4. The function f(n) = cn is clearly additive for an arbitrary n = ∑_{ν=0}^{k} e_{ν}F_{ν}^{∗}, (e_{ν} ∈ {0, 1}) representation since

f(n) = ∑_{ν=0}^{k} e_{ν}f(F_{ν}^{∗})

holds.

3 F-greedy (F^{∗}-greedy) additive and multiplicative functions

Let M be the set of all complex-valued multiplicative functions. We shall determine the sets M ∩ A_{F}^{(1)} and M ∩ A_{F^{∗}}, where A_{F^{∗}} is the set of all F^{∗}-greedy additive functions.

Theorem 5.

M ∩ A_{F^{∗}} = M ∩ A_{F}^{(1)} = {id},

where id(n) = n for every n ∈ ℕ.

Proof. Let f ∈ M ∩ A_{F^{∗}} and so f(1) = 1. First we show that

f(n) = n for n ≤ 11 and n = 144.  (7)

We list some initial members of F^{∗} that will be of use.

F_{0}^{∗} = 0, F_{1}^{∗} = 1, F_{2}^{∗} = 1, F_{3}^{∗} = 2, F_{4}^{∗} = 3, F_{5}^{∗} = 5, F_{6}^{∗} = 8, F_{7}^{∗} = 13, F_{8}^{∗} = 21, F_{9}^{∗} = 34, F_{10}^{∗} = 55, F_{11}^{∗} = 89 and F_{12}^{∗} = 144.

Let us call f(2) = x and f(3) = y. We have the following greedy expansions:

4 = 1 + 3 = F_{2}^{∗} + F_{4}^{∗},
6 = 1 + 5 = F_{2}^{∗} + F_{5}^{∗},
7 = 2 + 5 = F_{3}^{∗} + F_{5}^{∗},
9 = 1 + 8 = F_{2}^{∗} + F_{6}^{∗},
10 = 2 + 8 = F_{3}^{∗} + F_{6}^{∗},
14 = 1 + 13 = F_{2}^{∗} + F_{7}^{∗}.

Hence (utilizing f ∈ M ∩ A_{F^{∗}}),

f(4) = f(3) + 1 = y + 1,
f(5) = f(6) − 1 = f(2)f(3) − 1 = xy − 1,
f(7) = f(2) + f(5) = xy + x − 1,
f(8) = f(2)f(5) − f(2) = x^{2}y − 2x,
f(9) = f(1) + f(8) = x^{2}y − 2x + 1,
f(13) = f(14) − 1 = f(2)f(7) − 1 = x^{2}y + x^{2} − x − 1.

The expansions of 12, 15 and 18 are

12 = 1 + 3 + 8 = F_{2}^{∗} + F_{4}^{∗} + F_{6}^{∗},
15 = 2 + 13 = F_{3}^{∗} + F_{7}^{∗},
18 = 5 + 13 = F_{5}^{∗} + F_{7}^{∗}.

These give us,

f(3)f(4) = f(12) = f(1) + f(3) + f(8),
f(3)f(5) = f(15) = f(2) + f(13),
f(2)f(3)^{2} = f(18) = f(5) + f(13),

and finally the following three relations:

y^{2} − 1 − x^{2}y + 2x = 0,
(x + xy − 1)(−x + y − 1) = 0,
xy^{2} − xy − x^{2}y + 2 − x^{2} + x = 0.

We can conclude from the last three equations that

x = f(2) = 2, y = f(3) = 3.

Thus

f(n) = n for n ≤ 10.

Also, using

11 = 3 + 8 = F_{4}^{∗} + F_{6}^{∗}
165 = 21 + 144 = F_{8}^{∗} + F_{12}^{∗},

we obtain

f(11) = f(3) + f(8) = 3 + 8 = 11,
f(144) = f(3)f(5)f(11) − f(3)f(7) = 165 − 21 = 144.

Now we complete the proof of Theorem 5 by proving that if f(n) = n for every n < N (where N > 11) then

f(N) = N.

This assertion clearly holds true in the following two cases:

(1) if N is not a prime-power; or

(2) if N ∉ F^{∗}.

Thus let us assume that N = F_{m}^{∗} and that N = p^{α} for some α ∈ ℕ. It follows from the result of Bugeaud et al. [1] that if α ≥ 2, then N ∈ {1, 8, 144}. In all these Thus α = 1 and N > 11 is a prime. Let

2^{e}∥N + 1, 2^{ℓ}∥N + 3, e, ℓ ∈ ℕ.

Then min(e, ℓ) = 1. Assume that e = 1. Since 1 < \frac{N+1}{2} < N, we have

f(N + 1) = f(2)f(\frac{N + 1}{2}) = 2 · \frac{N + 1}{2} = N + 1.

Now,

f(N + 1) = f(F_{m}^{∗} + F_{2}^{∗}) =
= f(F_{m}^{∗}) + f(F_{2}^{∗}) =
= f(F_{m}^{∗}) + f(1) =
= f(F_{m}^{∗}) + 1.

However, from above, we know that f(N + 1) = N + 1, so f(F_{m}^{∗}) + 1 = N + 1, from which it follows that f(N) = f(F_{m}^{∗}) = N.

If ℓ = 1, then 1 < \frac{N+3}{2} < N, and we have

f(N + 3) = f(2)f(\frac{N + 3}{2}) = 2 · \frac{N + 3}{2} = N + 3.

Now,

f(N + 3) = f(F_{m}^{∗} + F_{4}^{∗}) =
= f(F_{m}^{∗}) + f(F_{4}^{∗}) =
= f(F_{m}^{∗}) + f(3) =
= f(F_{m}^{∗}) + 3,

from which it follows that f(N) = f(F_{m}^{∗}) = N.

Therefore, we have M ∩ A_{F^{∗}} = {id}. The proof of the assertion M ∩ A_{F}^{(1)} = {id} is similar and we omit it.

4 A Tribonacci-type sequence

A Tribonacci-type sequence G = (G_{n})_{n≥1}, which is a generalization of the Fibonacci sequence, is defined as follows:

G_{i} = i, for i = 1, 2, 3
G_{m+3} = G_{m+2} + G_{m+1} + G_{m} (m = 1, 2, …).  (8)

Remark 6. It is worth mentioning that a Tribonacci-type sequence (8) for us is 1, 2, 3, 6, 11, … whereas 1, 1, 2, 4, 7, 13, 24, 44, … is more familiar.

We aim to prove similar results as in the previous sections for G. Every integer n ∈ ℕ can be written as

n = ∑_{k=1}^{ℓ} e_{k}G_{k}, e_{k} ∈ {0, 1}.  (9)

In general n has more than one expansion. We can define the greedy and lazy expansion as follows:

n = ∑_{k=1}^{ℓ} ϵ_{k}G_{k} (greedy)

and

n = ∑_{μ=1}^{r} δ_{μ}G_{μ}, δ_{r} = 1 (lazy).

It is not hard to see that a sequence ϵ_{1}, …, ϵ_{k} is a sequence of the digits for a greedy expansion of some n ∈ ℕ if ϵ_{ν}ϵ_{ν+1}ϵ_{ν+2} ≠ 111 holds for every ν = 1, …, k − 2. Similarly, δ_{1}, …, δ_{r} (δ_{r} = 1) is a lazy expansion of some n ∈ ℕ if δ_{μ}δ_{μ+1}δ_{μ+2} ≠ 000 holds for every μ = 1, …, r − 2. We let lazyexp (G_{h}) denote the lazy expansion of G_{h}. Then

lazyexp(G_{h}) = \begin{cases}G_{h}, & if h = 1, 2, 3; \\ G_{h−1} + G_{h−2} + G_{h−3}, & if h = 4, 5. \end{cases}

If we write S_{k} = G_{1} + ⋯ + G_{k}, then

S_{1} = G_{1} = 1, S_{2} = 3, S_{3} = 6, S_{4} = 10

and

S_{k+4} = 2S_{k+3} − S_{k} for k ≥ 1.

If we set

L_{k} = G_{k+1} − S_{k−1} (k ≥ 2),

then

L_{k+1} − L_{k} = G_{k+2} − S_{k} − (G_{k+1} − S_{k−1}) = G_{k+2} − G_{k} − G_{k+1} = G_{k−1}.

Thus L_{k+1} − L_{k} > 0. Hence the largest component in the lazy expansion of G_{k+1} is G_{k} and therefore

lazyexp(G_{k+1}) = G_{k} + lazyexp(G_{k−1} + G_{k−2}).

If G_{k−1} + G_{k−2} ≤ S_{k−2}, then G_{k−1} ≤ S_{k−3}, which cannot occur if k ≥ 5. Thus

lazyexp(G_{k−1} + G_{k−2}) = G_{k−1} + lazyexp(G_{k−2}).

Let us assume now that g is G-additive for the greedy and lazy expansions, then with x_{k} = g(G_{k}), we obtain

x_{k+3} = x_{k+2} + x_{k+1} + x_{k} (k = 1, 2, …).

Now repeating the argument used in the proof of Theorem 2, we obtain

Theorem 7. Let g be a G-additive function for the greedy and for lazy expansion of the integers n ∈ ℕ. Let

g(n) = ∑_{k=1}^{ℓ} ϵ_{k}g(G_{k})

and

g(n) = ∑_{μ=1}^{r} δ_{μ}g(G_{μ}).

Then x_{h} = g(G_{h}) (h = 1, 2, …) satisfies

x_{h+3} = x_{h+2} + x_{h+1} + x_{h} (h = 1, 2, …).  (10)

On the other hand, if x_{h} is such a sequence for which (10) holds, then

g(n) = ∑_{k=1}^{ℓ} e_{k}g(G_{k})

holds for an arbitrary expansion (9) of n with e_{k} ∈ {0, 1}.

Finally we show that, Theorem 8. Let g be G-additive for the greedy expansion and that g is also a multiplicative function. Then g(n) = n for every n ∈ ℕ. Proof. The proof is a direct consequence of the following assertions: (A) g(n) = n for n ≤ 6; (B) If g(n) = n for every n < N, then g(N) = N. Assuming that (A) is proved, assertion (B) is clearly true, if N ≤ 6, or if N ∉ G, or if N ≠ prime power. Thus let us deal with the case when N = G_{m} = p^{α} for some prime p and N ≥ 7. If p = 2, then α ≥ 3, 2^{α−1} + 1 < 2^{α} = N and

N + 2 = G_{m} + G_{2}
= 2^{α} + 2
= 2(2^{α−1} + 1),

which gives

g(N + 2) = g(G_{m}) + 2
= g(2)g(2^{α−1} + 1)
= 2(2^{α−1} + 1)
= N + 2.

Consequently,

g(N) = g(G_{m}) = N.

If p > 2, then 2^{e}∥N + 1 = G_{m} + G_{1}, where \frac{N+1}{2^{e}} < N. If \frac{N+1}{2^{e}} > 1, then 2^{e} < N and so

g(N + 1) = g(G_{m}) + 1
= g(2^{e})g(\frac{N + 1}{2^{e}})
= N + 1.

This implies that

g(N) = g(G_{m}) = N.

If \frac{N+1}{2^{e}} = 1, then N = G_{m} = 2^{e} − 1 and 2^{e−1} + 1 < 2^{e} − 1 = N. Consequently,

g(G_{m}) + 3 = g(G_{m} + G_{3})
= g(2^{e} + 2)
= g(2)g(2^{e−1} + 1)
= G_{m} + 3.

Thus g(N) = g(G_{m}) = N.

It remains to prove assertion (A). Let ξ = g(2), η = g(3). It follows from (8) that

G_{1} = 1, G_{2} = 2, G_{3} = 3, G_{4} = 6, G_{5} = 11 and G_{6} = 20.

Now we use the facts that g is a G-additive function for the greedy expansion and g is also a multiplicative function and get

g(4) = g(G_{3}) + g(G_{1}) = η + 1,
g(5) = g(G_{3}) + g(G_{2}) = η + ξ,
g(7) = g(6) + g(1) = g(2)g(3) + 1 = ξη + 1,

and

g(11) = g(12) − g(1)
= g(3)g(4) − 1
= η^{2} + η − 1.

Again, using

10 = G_{4} + G_{3} + G_{1}
= 6 + 3 + 1,
14 = G_{5} + G_{3}
= 11 + 3,

and

28 = G_{6} + G_{4} + G_{2}
= 20 + 6 + 2,

we get the following system of equations:

ξ^{2} − η − 1 = 0
ξ^{2}η + ξ − η^{2} − 2η + 1 = 0
(η + 1)(ξη − 2ξ − η + 1) = 0.

The solutions of this system are ξ = 2 and η = 3. Therefore,

g(n) = n for n ∈ {1, 2, 3, 4, 5, 6, 7, 10, 11}.

This completes the proof of Theorem 8.

5 Acknowledgments

The authors are indebted to the anonymous referee for many suggestions/comments which have helped immensely to improve the presentation and to bring in more clarity.

References

[1] Y. Bugeaud, M. Mignotte, and S. Siksek, Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers. Ann. of Math. 163 (2006), 969–1018.

[2] L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr., Fibonacci representations of higher order. Fibonacci Quart. 10 (1972), 43–70.

[3] C. G. Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci. Simon Stevin, 29 (1951-1952), 190–195.

[4] A. Ostrowski, Bemerkungen zur Theorie der Diophantischen Approximationen. Abh. Math. Sem. Hamburg 1 (1922), 77–98.

[5] W. Steiner, The joint distribution of greedy and lazy Fibonacci expansions, Fibonacci Quart.. 43 (2005), 60–69 .

[6] S. Vajda, Fibonacci and Lucas Numbers, and the Golden Section, Theory and Applications, John Wiley & Sons, 1989.

[7] E. Zeckendorf, Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas. Bull. Soc. Roy. Sci. Liége 41 (1972), 179–182.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11A67. Keywords: Fibonacci sequence, Tribonacci sequence, greedy expansion, lazy expansion.

Received July 7 2015; revised versions received October 18 2015; October 29 2015; December 7 2015; April 18 2016; April 24 2016. Published in Journal of Integer Sequences, May 9 2016.

Return to Journal of Integer Sequences home page.