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.

## Contents

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

## References

## 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]