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