Semi-Fibonacci numbers

This article page is a stub, please help by expanding it.

The semi-Fibonacci numbers A030067 are defined by a(1) = 1, a(2n) = a(n), a(2n+1) = a(2n) + a(2n-1) = a(2n-1) + a(n), n ≥ 1. They start

A030067 = { 1, 1, 2, 1, 3, 2, 5, 1, 6, 3, 9, 2, 11, 5, 16, 1, 17, 6, 23, 3, 26, 9, 35, 2, 37, 11, 48, 5, 53, ... }.

They have their name due to the fact that odd-indexed terms have the same recurrent definition as the Fibonacci numbers, while the even-indexed terms have a simpler definition leading to a slower growth of the sequence, and to a somewhat more difficult analysis.

Occurrence of the positive integers

The first question that may rise naturally, is to ask which positive integers occur in this sequence, and where. We have the following results:

Prop.1: Any integer m which occurs in the sequence must first occur as an odd-indexed term a(2n-1). Indeed, if a(2n) = m, then a(n) = m.

Definition 1: Let us denote n(m) = min { n | a(2n-1) = m }. This defines an integer-valued function n(.) whose domain is the set of all semi-Fibonacci numbers, range(A030067). We could extend it to a integer sequence well defined on all (positive) integers by setting n(m) = 0 (instead of $-\infty$) whenever m does not occur at all. This yields sequence A284282.

Prop.2: If a(2n-1) = m, then a(n') = m for all n' = (2n-1)*2^k, k = 0,1,2,3.... This is obvious from the definition of the even-indexed terms.

Prop.3: For all m that occur in the sequence, we have a(n') = m if and only if n' ∈ (2*n(m)-1)*{ 2^k; k=0,1,2,... }. I.e., after its first occurrence, m will never again occur as an odd-indexed term, and thus at no other index different from that of its first occurrence multiplied by a power of 2.

This follows from the fact that the subsequence of odd-indexed terms (A030068) is strictly increasing, as shows their definition, a(2n+1) = a(2n-1) + a(n). This subsequence therefore equals the range or set of semi-Fibonacci numbers:

A030068 = { 1, 2, 3, 5, 6, 9, 11, 16, 17, 23, 26, 35, 37, 48, 53, 69, 70, 87, 93, 116, 119, 145, 154, 189, 191, ... }

This sequence S (with offset such that S(1) = 1) obeys the recurrent relation S(n+1) = S(n) + A030067(n).

See also

• Fibonacci numbers

Authorship

• This page was created on March 24 2017 by M. F. Hasler.

Cite this article as

M. F. Hasler, Semi-Fibonacci numbers.— From the On-Line Encyclopedia of Integer Sequences® Wiki (OEIS® Wiki). [https://oeis.org/wiki/Semi-Fibonacci_numbers]