A self-generating sequence

• Proves a conjecture from 2009 about a self-generating sequence. • Connects the sequence to the well-known paperfolding sequence. • Uses automata theory and a theorem-prover, instead of the usual proofs by induction. In 2009 the first author introduced a certain self-generating sequence ( a n ) n ≥ 1 = 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, …, with the property that the sum of the terms appearing in the n th run equals twice the n th term of the sequence. We give a connection between this sequence and the paperfolding sequence, and then prove a conjecture about the density of 1s appearing in ( a n ) n ≥ 1.

Authors

• Benoit Cloitre
• Jeffrey Shallit

Keywords

• Self-generating sequence
• Runs
• Finite automata
• Theorem-proving
• Paperfolding sequence