The toothpick sequence counts the total number of line segments after
stages of the following growth process. Stage 0 is empty, and stage 1 consists of
one vertical unit line segment. An endpoint
is exposed when it is neither an endpoint nor a midpoint
of any other line segment. At each subsequent stage,
a new unit line segment is centered at every exposed
endpoint, perpendicular
to the existing line segment there. All additions
in a stage are made simultaneously (Applegate et al. 2010).
Starting with , the totals are 0, 1, 3, 7, 11, 15, 23, 35, 43,
47, ... (OEIS A139250). The numbers added at
each stage are
for
, with
. These begin 0, 1, 2, 4,
4, 4, 8, 12, 8, 4, ... (OEIS A139251). They
satisfy
for nonnegative integers and
for integers with
(Applegate et al. 2010). The cumulative
totals are recovered as
. This local
growth rule provides a geometric example related to cellular
automata (Applegate et al. 2010, Numberphile 2018).