Leonardo number¶

A recurrence sequence beginning with one and one in which each later term is the sum of the previous two plus one.

Version: v2 · 2026-09-19 · History
Domain-specific #: 5302
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Discrete Mathematics → Mathematics

Core Idea¶

Leonardo numbers satisfy L-zero and L-one equal one and L-n equal L-n-minus-one plus L-n-minus-two plus one; they are closely related to shifted Fibonacci numbers and bound heap shapes in smoothsort. The inhomogeneous Fibonacci recurrence generates cumulative near-balanced subtree sizes, letting an algorithm represent heap orders and decompose array lengths efficiently. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

Add Two, Plus One

Start with 1 and 1. To get the next number, add the last two together and then add one more. So you get 1, 1, 3, 5, 9, 15, 25, and on and on. Computers use these numbers to build neat little piles of things when sorting.

Fibonacci's Plus-One Cousin

Leonardo numbers start with 1 and 1. Each new number is the two before it added together, plus 1, so you get 1, 1, 3, 5, 9, 15, 25, 41 and so on. They look a lot like Fibonacci numbers, but with that extra +1 each time. Computer scientists use them in a sorting method called smoothsort. There, they give the sizes of tree-shaped piles: two smaller piles joined under one extra item on top.

Smoothsort's Heap-Size Sequence

Leonardo numbers are defined by L(0) = L(1) = 1 and L(n) = L(n−1) + L(n−2) + 1, giving 1, 1, 3, 5, 9, 15, 25, 41, …. The extra +1 makes the recurrence inhomogeneous, unlike Fibonacci, though they're closely related to shifted Fibonacci numbers. The +1 has a natural meaning: a tree with a root and two subtrees of sizes L(n−1) and L(n−2) has L(n) nodes. Smoothsort builds heaps shaped like such nearly balanced trees and splits an array's length into Leonardo-number pieces. You must state your indexing and starting values before using formulas or smoothsort facts.

The Leonardo numbers satisfy the inhomogeneous Fibonacci-type recurrence L₀ = L₁ = 1, Lₙ = Lₙ₋₁ + Lₙ₋₂ + 1, giving 1, 1, 3, 5, 9, 15, 25, …. They are closely tied to Fibonacci numbers: Lₙ = 2Fₙ₊₁ − 1 with F₁ = F₂ = 1. Structurally, Lₙ counts the nodes of a near-balanced binary tree made of a root plus subtrees of order n−1 and n−2. Smoothsort maintains a forest of heaps with these sizes. Array prefixes can be decomposed into such heaps, and the set of orders present can be encoded compactly, which gives efficient insertion and extraction. Closed forms and smoothsort properties depend on stating the initial values and indexing explicitly, because a shifted or re-seeded sequence is a different object.

Scope of Application¶

Leonardo number belongs to discrete mathematics and is useful where the analyst can specify the typed discrete mathematics carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, then evaluate the initial values and plus-one recurrence are used consistently and indexing is stated before applying closed forms or smoothsort properties. The scope is broad within that domain but bounded by the need for the initial values and plus-one recurrence are used consistently and indexing is stated before applying closed forms or smoothsort properties. The entry records a descriptive analytical identity; practical use requires the governing domain's evidence, standards, and safety obligations.

Clarity¶

The abstraction clarifies a crowded vocabulary by making the initial values and plus-one recurrence are used consistently and indexing is stated before applying closed forms or smoothsort properties the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test. A bare label is insufficient because the name Leonardo number can be used for a formal identity, an implementation, or a neighboring result unless carrier and convention are stated.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Leonardo number. Leonardo number compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: the typed discrete mathematics carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express the initial values and plus-one recurrence are used consistently and indexing is stated before applying closed forms or smoothsort properties independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of discrete mathematics because they reuse the typed discrete mathematics carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, The inhomogeneous Fibonacci recurrence generates cumulative near-balanced subtree sizes, letting an algorithm represent heap orders and decompose array lengths efficiently., and type the carrier, state every parameter and convention in the definition, test that the initial values and plus-one recurrence are used consistently and indexing is stated before applying closed forms or smoothsort properties, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Leonardo number Domain-specific

Parents (1) — outgoing typed relations

Leonardo number is a kind of Recursion Prime

What makes it its own entry: the domain-specific identity determined by the initial values and plus-one recurrence are used consistently and indexing is stated before applying closed forms or smoothsort properties.

Hierarchy path (1) — routes to 1 parentless root

Leonardo number → is a kind of Recursion

Neighborhood in Abstraction Space¶

Leonardo number sits in a crowded region of the domain-specific corpus (15^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Numeral Systems & Integer Sequences (22 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25