A094913 extension

[David W. Wilson]

For n >= 0, k >= 0, let

       [1] f(n, k) = max(0, min(2^k, n-k+1))

Maximilian notes that f(n, k) bounds the number of distinct length-k 
substrings of a length-n binary string. If we let f(n) = A094913(n)+1 
be the number of distinct substrings of a length-n binary string, 
then we have

	[2] f(n) <= SUM(0 <= k <= n; f(n, k))

where Maximilian has conjectured equality.

We can actually prove equality for n = 2^m+m-1, for then there 
exists a binary string of length n that includes each of the possible 
2^m length-m binary substrings exactly once. This string can be shown 
to have precisely f(n, k) distinct length-k substrings for each 0 <= 
k <= n, and hence has f(n) total distinct substrings.

Now let us turn to A006697. A006697(n) is the number of distinct 
length-n substrings of the infinite word w starting with a and fixed 
by the substitution a -> aab, b -> b.

If we define the string-valued function

	[3] w(0) = a;  w(k+1) = w(k)w(k)b

then w(k) is the length-(2^(k+1)-1) prefix of w.

Let c(n, k) be the number of distinct length-n substrings of w whose 
first character lies in prefix w(k) of w, and legislate c(0, k) = 1.

Using [3], I am certain we can prove the empirical observation

	[4] c(n, k) = SUM(0 <= i <= k, f(n, i))

though the details are messy. One consequence of [4] is that c(n, m) 
= c(n, n) if m > n. From this, it follows that

	[5] A006697(n) = c(n, n).

But c(n, n) is precisely the sum in [2].  So, granting that [4] is 
indeed provable, all that remains is to prove Maximilian’s conjecture 
to obtain A006697(n) = A094913(n)+1 = SUM(0 <= k <= n; f(n, k)).