This site is supported by donations to The OEIS Foundation.

Semi-Fibonacci numbers

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 ${\displaystyle -\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).