Proofs of Several Conjectures From the OEIS

Sela Fried Department of Computer Science Israel Academic College in Ramat Gan Pinhas Rutenberg 87, Ramat Gan 52275 Israel

                      friedsela@gmail.com

Abstract We prove several conjectures from the On-Line Encyclopedia of Integer Sequences, concerned with constrained lattice point enumeration, pattern-avoiding words, roundingrelated formulas, and greedily defined sequences. Our methods are mostly elementary and include generating functions, recurrence analysis, and symbolic combinatorics.

1 Introduction

The On-Line Encyclopedia of Integer Sequences (OEIS) [7] is an indispensable tool for mathematicians and computer scientists. It catalogs over 385,000 sequences, many of which are accompanied by conjectural closed-form formulas, recurrence relations, generating functions, or asymptotic estimates. For example, Stephan [8] listed 100 such conjectures. These conjectures provide fertile ground for mathematical exploration, and their resolution can yield elegant combinatorial or analytic insights.

In this work, we prove several conjectures from the OEIS, covering a diverse range of topics and techniques. Specifically, we address problems from the following areas:

1. Lattice point enumeration. We compute the generating function corresponding to a certain constrained lattice points enumeration problem and extract exact formulas (cf. \underline{A371835}).

2. Pattern-avoiding words. We compute the generating functions corresponding to the enumeration of words over finite alphabets that avoid the patterns z, z + 1, z and z, z, z + 1 (cf. \underline{A005251} and \underline{A206790}).

3. Restricted repeating letters. We compute the generating function corresponding to the enumeration of words over finite alphabets with a certain restriction regarding repeating letters (cf. \underline{A269467}).

4. Rounding-related identities. We verify conjectured closed-form formulas for integer sequences involving central binomial coefficients and sums of cube roots (cf. \underline{A112884} and \underline{A136269}).

5. Median absolute deviation. We determine the asymptotic behavior of the median absolute deviation of a certain set, confirming the conjecture in \underline{A345318}.

6. Greedily defined sequences. Not directly addressing a conjecture, we prove that \underline{A128135} is a greedily defined sequence. We also propose our own conjecture related to the Fibonacci numbers (cf. \underline{A248982}).

Let us introduce some notation: The set of natural numbers {1, 2, …} is denoted by ℕ. For any real number x, the floor of x, denoted by ⌊x⌋, is the greatest integer less than or equal to x.

2 Lattice point enumeration

Let k and n be two nonnegative integers and let m ∈ ℕ. We let a_{n,k}^{(m)} denote the number of integer points (x_{1}, …, x_{m}), such that max_{1≤i≤m} |x_{i}| ≤ k and ∑_{i=1}^{m} |x_{i}| ≤ n. Sequence \underline{A371835} is concerned with the array (a_{n,k}^{(3)})\begin{matrix}n≥0 \\ 0≤k≤n \end{matrix}.

We let b_{n,k}^{(m)} denote the number of integer points (x_{1}, …, x_{m}), such that max_{1≤i≤m} |x_{i}| ≤ k and ∑_{i=1}^{m} |x_{i}| = n. For fixed k and m, we let B_{k}^{(m)}(x) denote the generating function for the numbers b_{n,k}^{(m)}. In the following theorem we calculate B_{k}^{(m)}(x). We then use this result to resolve and extend a conjecture stated in \underline{A371835}, regarding a closed-form formula for a_{n,k}^{(3)}.

Theorem 1. We have

B_{k}^{(m)}(x) = (1 + \frac{2x(1 − x^{k})}{1 − x})^{m} .  (1)

Proof. Clearly, b_{n,k}^{(m)} is also the number of compositions of n into m parts such that the absolute value of each part is ≤ k. We use the symbolic method (e.g., [2, I.3]). To this end, let I_{k} = {0, ±1, ±2, …, ±k} and let the size of an element in I_{k} be its absolute value. Then the corresponding generating function, for one part, is given by

I_{k}(x) = 1 + 2 ∑_{i=1}^{k} x^{i} = 1 + \frac{2x(1 − x^{k})}{1 − x}.

Consequently, the generating function for m parts is given by (I_{k}(x))^{m} and the assertion follows.

Corollary 2. We have

a_{n,k}^{(3)} =

\frac{1}{3} \begin{cases}4n^{3} + 6n^{2} + 8n + 3, & if 0 ≤ n < k; \\ 12k^{3} − 36k^{2}n + 36kn^{2} − 8n^{3} + 6n^{2} + 6k + 2n + 3, & if k ≤ n < 2k; \\ −84k^{3} + 108k^{2}n − 36kn^{2} + 4n^{3} − 72k^{2} + 72nk − 12n^{2} − 6k + 8n + 3, & if 2k ≤ n < 3k; \\ 24k^{3} + 36k^{2} + 18k + 3, & otherwise. \end{cases}

Proof. For fixed k and m, we let A_{k}^{(m)}(x) denote the generating function for the numbers a_{n,k}^{(m)}. Clearly, A_{k}^{(m)}(x) = B_{k}^{(m)}(x)/(1 − x). Thus

A_{k}^{(3)}(x) = \frac{−8x^{3k+3} + 12x^{2k+3} + 12x^{2k+2} − 6x^{k+3} − 12x^{k+2} − 6x^{k+1} + x^{3} + 3x^{2} + 3x + 1}{(1 − x)^{4}}.

Extracting coefficients, which is routine (e.g., [11, (2.5.7) on p. 53]), proves the stated formulas.

3 Pattern-avoiding words

3.1 Words avoiding the patterns z, z + 1, z and z, z, z + 1

The systematic study of words avoiding specific patterns was initiated by Guibas and Odlyzko [3]. Although the two cases considered here fall within the scope of their general results, we present direct and self-contained arguments. Let k ≥ 2 be an integer. We let [k] denote the set {1, 2, …, k}. For a nonnegative integer n, a word over k of length n is an element of [k]^{n}. A word w_{1} ⋯ w_{n} ∈ [k]^{n} is said to avoid the pattern z, z + 1, z if no 1 ≤ i ≤ n − 2 and z ∈ [k] exist such that w_{i} = w_{i+2} = z and w_{i+1} = z + 1. Avoidance of the other pattern z, z, z + 1 is defined similarly. We refer to a word avoiding the pattern in question as legal. The first part of the following theorem corresponds to \underline{A005251} by taking k = 2, to \underline{A098182} by taking k = 3 (giving the sequence a combinatorial interpretation), and to \underline{A206790} by taking k = 4 (proving the conjectures stated therein). The second part corresponds to \underline{A000071} by taking k = 2, to \underline{A206727} by taking k = 3 (proving the conjectures stated therein), and to \underline{A206570} by taking k = 4 (proving the conjectures stated therein).

Theorem 3.

(a) Let f_{k}(n) denote the number of words over k of length n that avoid the pattern z, z+1, z. Then, for n ≥ 3, the numbers f_{k}(n) satisfy the recursion

f_{k}(n) = kf_{k}(n − 1) − f_{k}(n − 2) + f_{k}(n − 3),

with initial values f_{k}(0) = 1, f_{k}(1) = k, and f_{k}(2) = k^{2}. In particular, the corresponding generating function is given by

\frac{1 + x^{2}}{1 − kx + x^{2} − x^{3}} .

(b) Let f_{k}(n) denote the number of words over k of length n that avoid the pattern z, z, z+1. Then, for n ≥ 2k − 1, the numbers f_{k}(n) satisfy the recursion

f_{k}(n) = ∑_{i=0}^{k−1}(−1)^{i}(k − i)f_{k}(n − 2i − 1).

Furthermore, the corresponding generating function is given by

\frac{1}{1 − ∑_{i=0}^{k−1}(−1)^{i}(k − i)x^{2i+1}} .

Proof.

(a) We derive the recurrence for f_{k}(n) as follows: To construct a legal word of length n, consider all legal words of length n − 1 and append one of the k letters. This gives kf_{k}(n−1) possibilities. However, some of these extensions may introduce the forbidden pattern at the end of the word. Such a pattern is created only when we append z +1, z to a legal word of length n − 2 ending with z. Thus, we must subtract f_{k}(n − 2) to remove these cases. This subtraction, however, erroneously includes cases where z = k (since k + 1 is not in the alphabet and hence the pattern k, k + 1, k cannot occur). Thus, we must add back the number of legal words of length n − 2 ending with k. These are precisely the words obtained by appending the letter k to a legal word of length n − 3. This gives the term f_{k}(n − 3).

(b) We derive the recurrence for f_{k}(n) using inclusion-exclusion as follows: To construct a legal word of length n, consider all legal words of length n − 1 and append one of the k letters. This gives kf_{k}(n − 1) possibilities. This extension however may introduce words having z, z, z + 1 at the end. Such words arise from legal words of length n − 3 by appending z, z, z + 1 for some z ≤ k − 1. Hence, we subtract (k − 1)f_{k}(n − 3). Now we need to add back words that end with z, z, z + 1, z + 1, z + 2 for some z ≤ k − 2, since they have an earlier occurrence of the pattern. Thus we add (k − 2)f_{k}(n − 5). Now we need to subtract words that end with z, z, z + 1, z + 1, z + 2, z + 2, z + 3 for some z ≤ k − 3 for the same reason. Thus, we subtract (k − 3)f_{k}(n − 7). Proceeding in this manner, the recursion follows.

3.2 Restricted repeating letters

In the following theorem we resolve some of the conjectures stated in \underline{A269467}. The sequence is concerned with the number of legal words over k of length n, denoted by f_{k}(n), where legal here means that no repeating letter is equal to the previous repeating letter (in particular, it is not allowed to have three consecutive equal letters). More precisely, a word w_{1} ⋯ w_{n} ∈ [k]^{n} is legal if for every 1 ≤ i < j ≤ n − 1 and s ∈ [k], such that w_{i} = w_{i+1} = w_{j} = w_{j+1} = s, there exist i < m < j and t ∈ [k] such that t ≠ s and w_{m} = w_{m+1} = t. For example, the word 11233 is legal while the words 111233 and 11211 are not.

Theorem 4. Let F_{k}(x) denote the generating function for the sequence (f_{k}(n))_{n≥1}. Then

F_{k}(x) = −\frac{(k − 2)x^{3} + 2(k − 2)x^{2} + (k − 3)x − 1}{2(k − 1)^{2}x^{3} + (k − 1)(k − 4)x^{2} + (3 − 2k)x + 1}.  (2)

Proof. Let 0 ≤ u ≤ k and 1 ≤ v ≤ k. We let f_{k,u,v}(n) denote the number of legal words over k of length n whose last letter is v and whose last repeating letter is u. Notice that u = 0 encodes legal words having no repeating letters at all and therefore ∑_{v=1}^{k} f_{k,0,v}(n) = k(k − 1)^{n−1}. For n ≥ 3 we have

f_{k,u,v}(n) = \begin{cases}∑_{1≤t≤k,t≠v} f_{k,u,t}(n − 1) + ∑_{0≤t≤k,t≠v} f_{k,t,u}(n − 1), & if v = u; \\ ∑_{1≤t≤k,t≠v} f_{k,u,t}(n − 1), & if v ≠ u. \end{cases}

Then

f_{k}(n) = ∑_{u=0}^{k} ∑_{v=1}^{k} f_{k,u,v}(n)

= ∑_{u=0}^{k} ∑_{v=1}^{k} ∑_{1≤t≤k,t≠v} f_{k,u,t}(n − 1) + ∑_{v=1}^{k} ∑_{0≤t≤k,t≠v} f_{k,t,v}(n − 1)

= ∑_{v=1}^{k} ∑_{u=0}^{k} (∑_{t=1}^{k} f_{k,u,t}(n − 1) − f_{k,u,v}(n − 1)) + ∑_{v=1}^{k} (∑_{t=0}^{k} f_{k,t,v}(n − 1) − f_{k,v,v}(n − 1))

= kf_{k}(n − 1) − ∑_{v=1}^{k} f_{k,v,v}(n − 1).  (3)

Now

∑_{v=1}^{k} f_{k,v,v}(n − 1) = ∑_{v=1}^{k} (∑_{t=1}^{k} f_{k,v,t}(n − 2) + ∑_{t=0}^{k} f_{k,t,v}(n − 2) − 2f_{k,v,v}(n − 2))

= 2f_{k}(n − 2) − ∑_{t=1}^{k} f_{k,0,t}(n − 2) − 2 ∑_{v=1}^{k} f_{k,v,v}(n − 2)

= 2f_{k}(n − 2) − k(k − 1)^{n−3} − 2 ∑_{v=1}^{k} f_{k,v,v}(n − 2).  (4)

Iterating (4) until we reach ∑_{v=1}^{k} f_{k,v,v}(2), which is equal to k, and substituting the result into (3), we obtain the equation

f_{k}(n) = kf_{k}(n − 1) + ∑_{i=1}^{n−3} ((−2)^{i}f_{k}(n − 1 − i) + (−2)^{i−1}k(k − 1)^{n−2−i}) − (−2)^{n−3}k.

Multiplying both sides of the equation by x^{n} and summing over n ≥ 4, we may (eventually) solve for F_{k}(x) and obtain (2).

Corollary 5. The denominator of F_{k}(x) confirms the conjectured recurrences stated in \underline{A269467}.

4 Rounding-related identities

4.1 The number of bits required to represent \binom{2^{n}}{2^{n−1}}

The statement of the following theorem was conjectured in \underline{A112884}.

Theorem 6. Let n ∈ ℕ. The number of binary bits required to represent \binom{2^{n}}{2^{n−1}} is 2^{n}−⌊n/2⌋.

Proof. The number of binary bits required to represent a nonnegative integer m is ⌊log_{2} m⌋+ 1. Now the number \binom{2^{n}}{2^{n−1}} is actually a central binomial coefficient, for which many bounds exist. We use the following elementary bound stated in [9, (21)]:

\frac{4^{m}}{\sqrt{4m}} < \binom{2m}{m} < \frac{4^{m}}{\sqrt{3m + 1}}, m ∈ ℕ.

Plugging m = 2^{n} and applying the logarithm, we then have

2^{n} − \frac{n}{2} − \frac{1}{2} < log_{2} \binom{2^{n}}{2^{n−1}} < 2^{n} − \frac{n}{2} + \frac{1}{2} − \frac{1}{2} log_{2} 3 ≈ 2^{n} − \frac{n}{2} − 0.292,

from which the assertion immediately follows.

4.2 The floor of the sum of the first 10^{n} cube roots

The statement of the following theorem was conjectured in \underline{A136269}.

Theorem 7. Let n ∈ ℕ be divisible by 3. Then

⌊∑_{i=1}^{10^{n}} \sqrt[3]{i}⌋ = \frac{3 · 10^{4n/3}}{4} + 5 · 10^{n/3−1} − 1.

Proof. For every m ∈ ℕ and any real r ≥ 1, we have by [6],

∑_{i=1}^{m} i^{\frac{1}{r}} = \frac{r}{r + 1}(m + 1)^{\frac{1+r}{r}} − \frac{1}{2}(m + 1)^{\frac{1}{r}} − ϕ_{m}(r),

where 0 ≤ ϕ_{m}(r) ≤ \frac{1}{2}. Taking r = 3 and m = 10^{n} − 1, we obtain

\frac{3 · 10^{4n/3}}{4} − \frac{10^{n/3}}{2} − \frac{1}{2} ≤ ∑_{i=1}^{10^{n}−1} \sqrt[3]{i} ≤ \frac{3 · 10^{4n/3}}{4} − \frac{10^{n/3}}{2} .  (5)

Adding \sqrt[3]{10^{n}} to (5) proves the assertion.

5 Median absolute deviation

Sequence \underline{A345318} is concerned with a statistical measure of spread, called the median absolute deviation (e.g., [4, p. 291]), of the set {2k^{2} : k = 1, …, n}. Notice that the purpose of the factor 2 in 2k^{2} is merely to ensure that the resulting sequence is an integer sequence. We omit this factor in our analysis.

Theorem 8. Let n ∈ ℕ and set A_{n} = {k^{2} : k = 1, 2, …, n}. Let a_{n} denote the median absolute deviation of A_{n}, i.e.,

a_{n} = median({|x − median(A_{n})| : x ∈ A_{n}}).

Then lim_{n→∞} a_{n}/n^{2} = \sqrt{3}/8.

Proof. Let m_{n} = median(A_{n}). Then m_{n} = n^{2}/4 + O(n). Let δ ∈ (0, 1/4) and let N(n, δ) denote the number of values of k such that |k^{2} − m_{n}| ≤ δn^{2}. Then

N(n, δ) = \sqrt{m_{n} + δn^{2}} − \sqrt{m_{n} − δn^{2}} + O(1).

Thus,

\frac{N(n, δ)}{n} = \sqrt{\frac{1}{4} + δ + O (\frac{1}{n})} − \sqrt{\frac{1}{4} − δ + O (\frac{1}{n})} + O (\frac{1}{n}) ⟶_{n→∞} \sqrt{\frac{1}{4} + δ} − \sqrt{\frac{1}{4} − δ}.

The equation

\sqrt{\frac{1}{4} + δ} − \sqrt{\frac{1}{4} − δ} = \frac{1}{2}

has a unique solution in (0, 1/4), namely, \sqrt{3}/8, and the assertion follows.

6 Greedily defined sequences

In the following theorem we show how sequence \underline{A128135} emerges as a subsequence of a sequence defined by a greedy integer recurrence. Such greedily defined integer sequences have been studied by Venkatachala [10], Avdispahić and Zejnulahi [1], and Shallit [5]. While the result we obtain does not directly settle a conjecture from the OEIS, we observed it while working on a conjecture stated in \underline{A248982}. We shall elaborate on it at the end of this section.

Theorem 9. Let a_{1} = 1 and, for n ≥ 2, let a_{n} be the least positive integer such that the average of a_{1}, …, a_{n−1} is a power of 2. Then

a_{n} = \begin{cases}(n + 1)2^{\frac{n}{2} −1}, & if n is even; \\ 2^{\frac{n−1}{2}} , & otherwise. \end{cases}

Proof. Set s_{n} = ∑_{i=1}^{n} a_{i}. We claim that s_{n} = n2^{⌊^{\frac{n}{2}}⌋} (this sequence is \underline{A132344}). To see that, we proceed by induction on n. The base case, namely n = 1, obviously holds. Now assume that the assertion holds for every 1 ≤ i ≤ n − 1, where n ≥ 2. Let ℓ be a nonnegative integer such that s_{n} = n2^{ℓ}. We have

a_{n} = s_{n} − s_{n−1} = n2^{ℓ} − (n − 1)2^{⌊^{\frac{n−1}{2}}⌋}.  (6)

Clearly, if ℓ ≥ ⌊(n − 1)/2⌋, then a_{n} > 0. We claim that the converse also holds. Indeed, suppose that a_{n} > 0 but ℓ < ⌊(n − 1)/2⌋. Then

n2^{⌊^{\frac{n−1}{2}}⌋−1} − (n − 1)2^{⌊^{\frac{n−1}{2}}⌋} > 0 ⟺ \frac{n}{n − 1} > 2.

But since n ≥ 2, we have n/(n − 1) ≤ 2.

Now assume that n is even. If ℓ = ⌊(n−1)/2⌋, then, by (6) and the induction hypothesis, a_{n} = 2^{⌊^{\frac{n−1}{2}}⌋} = 2^{\frac{n−2}{2}} = a_{n−1}, in violation of the distinctness condition. Trying the next best candidate ℓ = ⌊(n − 1)/2⌋ + 1, we have, by (6),

a_{n} = n2^{⌊^{\frac{n−1}{2}}⌋+1} − (n − 1)2^{⌊^{\frac{n−1}{2}}⌋} = (n + 1)2^{⌊^{\frac{n−1}{2}}⌋},

which is obviously adequate. Thus, s_{n} = n2^{⌊^{\frac{n}{2}}⌋}.

Now consider a_{n+1} and let ℓ be a nonnegative integer such that s_{n+1} = (n + 1)2^{ℓ}. We have

a_{n+1} = s_{n+1} − s_{n} = (n + 1)2^{ℓ} − n2^{⌊^{\frac{n}{2}}⌋}.

Here, ℓ = ⌊n/2⌋ is possible, leading to a_{n+1} = 2^{⌊^{\frac{n}{2}}⌋} and s_{n+1} = (n + 1)2^{⌊^{\frac{n}{2}}⌋}, concluding the proof of the induction step.

As mentioned earlier, we observed the statement of the previous theorem while working on a conjecture stated in \underline{A248982}, which is defined to be the sequence of distinct least positive numbers such that the average of the first n terms is a Fibonacci number. Let (a_{n})_{n≥1} be this sequence. Refining the conjecture stated in \underline{A248982} regarding a closed-form formula for (a_{n})_{n≥1}, it seems that, for n ≥ 10, we have

a_{n} = \begin{cases}nF (\frac{n}{2} + 3) − (n − 1)F (\frac{n}{2} + 2) , & if n is even; \\ F (\frac{n+1}{2} + 2) , & otherwise. \end{cases}

A proof of this likely proceeds along similar lines as the previous theorem. Nevertheless, we were not able to show that the two sets

\{nF (\frac{n}{2} + 3) − (n − 1)F (\frac{n}{2} + 2) : n ≥ 1 is even\} ,

\{F (\frac{n + 1}{2} + 2) : n ≥ 1 is odd\} ,

are disjoint, or, equivalently, that for every n ∈ ℕ, the number F (n + 2) + 2nF (n + 1) is not a Fibonacci number. We conjecture that this is so. Notice that a similar sequence is the Les Marvin sequence \underline{A007502}(n) = F (n) + (n − 1)F (n − 1).

7 Acknowledgments

The author is grateful to the anonymous referee for their careful reading of the manuscript and for their valuable suggestions, which led to substantial simplifications of several of the proofs.

References

[1] M. Avdispahić and F. Zejnulahi, An integer sequence with a divisibility property, Fibonacci Quart. 58 (2020), 321–333.

[2] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[3] L. J. Guibas and A. M. Odlyzko, String overlaps, pattern matching, and nontransitive games, J. Combin. Theory Ser. A 30 (1981), 183–208.

[4] D. C. Hoaglin, F. Mosteller, and J. W. Tukey, Understanding Robust and Exploratory Data Analysis, John Wiley & Sons, 2000.

[5] J. Shallit, Proving properties of some greedily-defined integer recurrences via automata theory, Theoret. Comput. Sci. 988 (2024) 114363.

[6] S. Shekatkar, The sum of the r’th roots of first n natural numbers and new formula for factorial, arXiv preprint arXiv:1204.0877 [math.GM], 2012. Available at

https://arxiv.org/abs/1204.0877.

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, OEIS Foundation Inc.,

https://oeis.org, 2025.

[8] R. Stephan, Prove or disprove. 100 conjectures from the OEIS, arXiv preprint math/0409509 [math.CO], 2004. Available at https://arxiv.org/abs/math/0409509.

[9] I. V. Tikhonov, V. B. Sherstyukov, and D. G. Tsvetkovich, Comparative analysis of twosided estimates of the central binomial coefficient, Chelyab. Fiz.-Mat. Zh. 5 (2020), 70– 95.

[10] B. J. Venkatachala, A curious bijection on natural numbers, J. Integer Sequences 12 (2009), Article 09.8.1.

[11] H. S. Wilf, generatingfunctionology, 2nd ed., Academic Press, Inc., 1994. Available

online at https://www.math.upenn.edu/~wilf/gfology2.pdf.

2020 Mathematics Subject Classification: Primary 11B99; Secondary 05A15. Keywords: generating function, lattice point, pattern-avoidance.

(Concerned with sequences \underline{A000071}, \underline{A005251}, \underline{A006190}, \underline{A007502}, \underline{A098182}, \underline{A112884}, \underline{A128135}, \underline{A132344}, \underline{A136269}, \underline{A138365}, \underline{A206570}, \underline{A206727}, \underline{A206790}, \underline{A248982}, \underline{A269467}, \underline{A294139}, \underline{A294172}, \underline{A307684}, \underline{A309878}, \underline{A345318}, and \underline{A371835}.)

Received November 27 2024; revised versions received November 28 2024; July 7 2025; July 15 2025. Published in Journal of Integer Sequences, August 2 2025.

Return to Journal of Integer Sequences home page.