Starter Constants & Mysteries
For a long time, about 10 years now (!), I have
been interested in what happens when you take differences between
adjacent terms in a sequence, for example:
0, 1, 4, 9, 16, 25, 36, 49…
1, 3, 5, 7, 9, 11, 13…
2, 2, 2, 2, 2, 2…
the first sequence is y = n^2, and each successive sequence is the
difference between adjacent terms in the previous sequence. Taking any
further differences produces the zero function, y = 0.
We can do this for any sequence f(n), where f1(n) = f(n+1) - f(n), f2(n) = f1(n+1) - f(n), and in general fx(n) = fx-1(n+1) - fx-1(n), until for some value of x fx(n)
= k, for some constant k. (I won’t be using the subscripts much,
because tumblr recently made it very hard to insert any kind of
formatting into a post, which is why the sequences above aren’t in a
monospace font, even though they should be.)
have been interested in the first terms in these sequences (what I call
“starter constants”), that is, f(0), f1(0), f2(0), and looking for
patterns in them. Here is what I found.
Starter constants of powers
main objective was to find a pattern among the starter constants of
n^k, for integers k, akin to Pascal’s triangle or something. This was
partially because they were increasingly hard to calculate for higher
values of k, but also because just by looking at them they seemed to be
filled with patterns that I couldn’t find. Here is the difference table
for the 4th powers:
0, 1, 16, 81, 256, 625 1296, 2401…
1, 15, 65, 175, 369, 671, 1105…
14, 50, 110, 194, 302, 434…
36, 60, 84, 108, 132…
24, 24, 24, 24…
so the starter constants are 0, 1, 14, 36, 24.
note: I used to calculate the starter constants starting at f(1), so I
would have computed this as: 1, 15, 50, 60, 24. How they change with
different “offsets” of the same sequence will become relevant later.)
first things I noticed were that the nth powers have n! as their last
starter constant, and 0, 1, and 2^n - 2 as their first three. But for a
long time I couldn’t find any other patterns.
A new approach
forward to 2011. I was just getting out of the shower when I suddenly
realized that the SC’s for the cubes – 0, 1, 6, and 6 – were divisible
by 0, 1, 2, and 3 respectively. I tried dividing the last 3 by 1, 2,
and 3, and I got:
1, 3, 2
Suddenly I realized something. 1,
3, AND 2 WERE JUST THE STARTER CONSTANTS OF THE SQUARES WHEN YOU STARTED
AT 1^2 INSTEAD OF 0!!!! I wondered if the same thing worked for other
powers. So I tried the fourth power SC’s – 0, 1, 14, 36, 24 – and I
got 1, 7, 12, and 6, which were indeed the starter constants of (x +
I finally had what seemed to be a method for getting the
n+1st power starter constants from the nth ones, and indeed the starter
constants of n*f(n) from those of f(n) for any sequence f(n). Here is
how it works:
- List the SC’s for f(x) starting at x = 1, and append an extra number to the beginning (any number will do).
can be accomplished by taking the SC’s from x = 0 and adding adjacent
terms as in Pascal’s Triangle to form a string of numbers one longer.
- Multiply the nth term (starting from the top at n = 0) by the number n.
- You now have the SC’s for x*f(x), starting at x = 0.
For example, say you have a sequence with the SC’s 7, 3, 5, 4.
The difference table for such a sequence would go like this:
7, 10, 18, 35, 65, 112… (sequence itself)
3, 8, 17, 30, 47… (first differences)
5, 9, 13, 17… (second differences)
4, 4, 4… (third differences, constant sequence)
Adding adjacent starter constants gives you:
7, 10, 8, 9, 4
Now multiply by 0, 1, 2, 3, 4:
0, 10, 16, 27, 16.
Which gives the sequence:
0, 10, 36, 105, 260, 560, 1080…
And the differences:
10, 26, 69, 155, 300, 520…
16, 43, 86, 145, 220…
27, 43, 59, 75…
16, 16, 16…
which is indeed x*f(x)!
But I still didn’t have a proof that it always worked. And that, I knew, is what would solve the mystery.
The starter constant mystery gets solved
spring 2012, I started making good progress on solving the starter
constant mystery, and finally, on June 20, 2012, I solved it! The proof
is too long to write here, but all my logic is written down on pieces of
paper in my room.
Also, I’ll probably be writing another proof soon. More on that later.
Uses in algebra
the SC’s for the powers is very useful. Say we know a sequence by its
SC’s, and we want to figure out its polynomial. We can form the SC’s by
adding scaled versions of the SC’s for the powers, and the scaling
factors will be the coefficients for the polynomial. For example, say we
wanted to find the polynomial for our sequence earlier, with the SC’s
7, 3, 5, 4.
First of all, since 0, 1, 6, 6 are the SC’s for the cubes, 0, 2/3, 4, 4 are the SC’s y = 2/3*x^3.
1, 2 are the SC’s for the squares, so 0, ½, 1 are the SC’s for y =
½*x^2, and adding this to 2/3*x^3 with the SC’s 0, 2/3, 4, 4 gives us
0, 7/6, 5, 4, the SC’s for y = 2/3*x^3 + ½*x^2.
0, 11/6 are the SC’s for y = 11/6*x, so 0, 3, 5, 4 are the SC’s for y = 2/3*x^3 + ½*x^2 + 11/6*x.
finally, 7 is the SC for y = 7, so 7, 3, 5, 4 are the SC’s for y =
2/3*x^3 + ½*x^2 + 11/6*x + 7. It is common for polynomials that
generate integers to have non-integer coefficients like this.
you know the SC’s of a polynomial f(x), it is also possible to figure
them out for f(x)/x, assuming f(x)/x reduces to a polynomial itself. To
do this we just have to apply the method for finding the SC’s of x*g(x)
based on those for g(x) in reverse:
Say the SC’s for f(x) are 0,
a, b, c, d … m, n. (The first one has to be 0 in order for f(x) to be
divisible by x.) Then this is how the SC’s for f(x)/x are found:
a by 1, b by 2, c by 3… all the way up to n by i[n], where i[n] is
the index of n, and replace the zeroth SC by the undefined value 0/0.
You should get 0/0, a, b/2, c/3, d/4, … n/i[n].
Now replace each term (except for 0/0) by the alternating sum of the terms from it to i[n], to get (from bottom to top):
(n-1)/i[n-1] - n/i[n]
(n-2)/i[n-2] - (n-1)/i[n-1] + n/i[n]
all the way up to…
a - b/2 + c/3 … ± n/i[n].
These are the SC’s for f(x)/x, with a - b/2 + c/3 … ± n/i[n] being the zeroth and working upward.
for one thing. The zeroth SC of a sequence s(x) is always equal to
s(0). But f(0)/0 is undefined. As it turns out, the zeroth SC here:
a - b/2 + c/3 … ± n/i[n]
is the limit of f(x)/x as x goes to 0. So this is also a way to find the limit of f(x)/x as x goes to 0, by looking at just the SC’s.
A surprising theorem
f(x) is a polynomial sequence with integer starter constants and f(0) =
0, then for only a finite number of primes p will f(p)/p not be an
This certainly surprised me, the fact that you could
take any sequence of integers and, as long as there were a finite number
of SC’s and the zeroth one was 0, high enough primes p would always be
factors of the pth term in the sequence. For example:
0, 1, 8, 28, 68, 135, 236, 378…
1, 7, 20, 40, 67, 101, 142…
6, 13, 20, 27, 34, 41…
7, 7, 7, 7, 7…
28 is not divisible by 3, but 8/2 = 4, 135/5 = 27, 378/7 = 54, and all higher primes will divide their terms too.
see why this works, look at the SC’s for f(x)/x (or, more precisely,
the limit of f(h) over h as h -> x). From the formula given above:
(n-1)/i[n-1] - n/i[n]
(n-2)/i[n-2] - (n-1)/i[n-1] + n/i[n]
a - b/2 + c/3 … ± n/i[n].
is clear that the denominator of the gth SC will be a factor of the
product of the integers from g to i[n], as it is formed by adding
fractions with denominators from g to i[n]. (Remember a, b, c … n are
the SC’s of the original function, which we specified were integers.)
But all of the denominators are factors of i[n]! (and also the LCM of
the integers from 1 to i[n]), so the denominators of the terms
themselves are factors of that number too. But for any prime number p
which cannot be a factor of the denominator, f(p) is an integer and so
the denominator of the simplest form of f(p)/p must be a factor of p.
But since p is not a factor of the maximum possible denominator, the
only number that can be a factor of both is 1. So the simplest form of
f(p)/p has a denominator of 1, and is therefore an integer. This can be
repeated for all primes the denominators are not divisible by, which is all
but a finite number of primes.
The second starter constant mystery
Back to the mysteries. In April 2015, almost 3 years after solving the original starter constant mystery, I happened to be searching for starter constant of the 6th powers when I found the triangle of SC’s, read line by line, as sequence A090582 in the OEIS! The description they gave was:
Numerator Q(m,n) of probability P(m,n)=Q(m,n)/n^m of
seeing each card at least once if m>=n cards are drawn with
replacement from a deck of n cards, written in a two-dimensional array
read by antidiagonals with Q(m,m) as first row and Q(m,1) as first
That was strange. They had the exact same elusive sequence, but with a different definition! Maybe I could prove the two definitions were equivalent and get another way to calculate the SC’s. I might even be able to find a simpler proof of the original starter constant mystery!
I translated their definition, and made the following conjecture:
“The bth starter constant of the ath powers is the number of ways to choose a cards from a stack of b, with replacements, and get every single card.”
I knew this was true when b = 1, because there is only one way to choose one card from a set of a cards, no matter what a is. I also knew it was true for b = 2, because the 2nd SC of the ath powers is 2^a - 2, and out of the 2^a ways there would be to choose and replace a cards from a deck of two, the only two that wouldn’t get both cards chosen were selecting the same card repeatedly, making 2^a - 2 ways to get both cards.
So I tried to prove this for all values of a and b. After hitting a dead end about summation of binomial coefficient products, I decided to take a break, but on June 2, 2015, I suddenly had a glorious insight that led to a solution!
Proof of the second SCM
First of all, I will
henceforth explain this in terms of “strings of a digits in base b”
instead of choosing and replacing a cards from a set of b, to emphasize
that the order of the card-choosing matters, and to number every card in
the set from 0 to b-1.
Okay. So first of all, the number of
a-digit strings in base b is b^a. (Here, when we say “a-digit strings”,
we mean “strings of a or less digits”, i.e. the first digit can be 0,
analogous to the choosing of cards. Or we could be using definite-length
base b, with digits 1 through b - see the last post.) If a holds a
constant value (not to be confused with the property of being a starter
constant), which it will throughout the proof, then y = b^a is a
function determining the number of a-digit strings in base b. That’s
pretty obvious, isn’t it?
Even when b = 0, the range of digits 0 ≤
d < b is the null set, which means there are 0 possible a-digit
strings. So that works out too.
Now let’s study the differences between the nth set and the (n-1)st set.
each digit string in the set of digit strings for base b is also in the
set for base b+1, the cardinality of the differences between the two
sets is the difference of the cardinalities, or in other words, (b+1)^a -
What would this set represent? Why, it would represent the
digit strings that used only digits in base b+1, but did not use only
digits in base b. In other words, it was the set of digit strings that
used only digits from 0 to b, and included b.
So there are (b+1)^a
- b^a strings of digits in base b+1, that use the digit b. This is
actually the number of strings in base b+1 that have one fixed digit, no
matter what it is. Substituting b for 0, we can see that this is also
the number of base-b+1 digit strings that use the digit 0.
For b =
0, this describes the 1st SC (= 1^a - 0^a) as the number of base-1
strings that use the one specific digit, say 0; that is, all base-1
strings, because 0 is the only digit they can use. But this is also the
number of base-1 strings that use every digit. So we proved the
(trivial) case of our theorem for b = 1.
Let’s call x^a f(x). Now
(b+1)^a - b^a = f1(b), from the notation at the beginning, and f1(b+1) -
f1(b) = f2(b). We want to prove that f2(0) is the number of base-2
a-digit strings that use both digits 0 and 1.
First notice that
since f1(b) represents the number of base-b+1 strings using 0, f2(b)
represents the number of base-b+2 strings using 0 minus the number of
base-b strings using 0. Since all base-b+1 strings are base-b+2 strings,
this is the same as the number of base-b+2 strings using the digit 0
that are not valid base-b strings, which in turn is the same as the
number of base-b+2 strings that use the digits 0 and b. Finally, we can
substitute b+1 for 1 and say that this is the number of base-b+2 strings
that use the digits 0 and 1.
Continuing this way, we can prove by induction that fn(b)
is the number of base-b+n strings that use the first n digits (or any
set of n digits in the valid range from 0 to b + n - 1).
This means that fn(0), i.e. the nth starter constant of the ath powers, is the number of base-n strings that use the first n digits, in other words, all n digits from 0 to n-1. QED.
Usage in probability
This unexpectedly related the SC’s to a problem I had been wondering about since 2012.
How many people need to be in a room for there to be more than a 50% chance that people born on all 365 days (excluding Leap Day) are present?
If you know about the birthday paradox, you should know if there are 365 (non-Leapie) people in the room, the probability of no two people sharing a birthday, which is the same as all 365 common birthdays being covered, is 365!/365^365, or only
1.454955215618703403371401590385251600494220164 × 10^-157.
It is also obvious that if there are 100000 people in a room, there’s a very good chance that each possible birthday gets covered many times. But when does the chance pass ½?
To do this you need to calculate the 365th SC’s of the nth powers, which can be expressed as 365^n - 365*364^n + 365C2*363^n - 365C3*362^n…, where 365Cn is 365 choose n, the nth binomial coefficient on the 365th row of Pascal’s Triangle, until one of them exceeds ½*365^n, and then the answer is n.
That is too difficult even for me (but at least I know how to calculate it), so let’s try a simpler problem.
How many people do you need before it becomes likely that you have one born on each day of the week?
To answer this problem, you would need to look at the SC’s for the 7th powers, because there are 7 days in a week. If we number the days of the week from 0 to 6, the week days the people were born on could be represented as a base-7 number. We need to find the minimum number of digits such that it is likely that the number will use every digit from 0 to 6. Since there are 7^a possible a-digit strings, we need to find the smallest value of a such that the 7th SC of the ath powers is more than half of 7^a.
If we use the formula for the 7th SC as 7^a - 7*6^a + 21*5^a - 35*4^a + 35*3^a - 21*2^a + 7, we can figure out that this transition happens for the a=17, when the 7th SC is 129568848121440, and 7^17 = 232630513987207. So 17 is the minimum number of people needed in order for it to be likely that there are ones born on each day of the week.
Where to next?
Now that I’ve proved the starter constant mystery and the second starter constant mystery, what will I do next? There are still mysteries out there. For example, the SC’s are actually listed thrice in the OEIS, each under a different rearrangement of the terms, and they give a different definition as well under A019538:
Triangle of numbers T(n,k) = k!*Stirling2(n,k) read by rows (n >= 1, 1 <= k <= n).
So, as it turns out, the nth SC isn’t just divisible always divisible by n (which is an obvious corollary of the starter constant mystery), it’s divisible by n! as well! This sounds like it could be a nice thing to prove too.
I will probably also be using the second starter constant mystery to make a simpler proof for the first one – most likely on June 20, for the third anniversary of the original solution.
Table of the starter constants up to the 10th powers