This post has a pretty weird title, but the problem is easy to state and uses a few interesting mathematical concepts.  It’s worth going through.  Let’s start with the basics.


Problem 1.  Let S_{\alpha}(n) = 1^{\alpha} + 2^{\alpha} + \dots + n^{\alpha}.  Show that S_{\alpha}(n) is a polynomial for each \alpha\in {\mathbb N} and that the degree of the polynomial is \alpha + 1.


Indeed, for example, we have  that 1 + 2 + \dots + n = \frac{n(n+1)}{2}, as we learned in Calculus, and this is a polynomial of degree 2.  Similarly, 1^{2} + 2^{2} + \dots + n^{2} = \frac{n(n+1)(2n+1)}{6}, which is a polynomial of degree 3.  In the same respect, 1^{3} + 2^{3} + \dots + n^{3} = \frac{(n(n+1))^{2}}{4}, which is a polynomial of degree 4.

The associated polynomials in this case are given by Faulhaber’s formula:


Theorem (Faulhaber).  For \alpha\in {\mathbb N} we have \displaystyle \sum_{k=1}^{n}k^{\alpha} = \frac{1}{1 + \alpha}\sum_{j=0}^{\alpha}(-1)^{j}\binom{\alpha + 1}{j}B_{j}n^{\alpha + 1 - j}.


This formula looks terrifying, but it is not hard to apply in practice.  You may be wondering, though, what the B_{j}‘s in this formula stand for.  These are the strange and wonderful Bernoulli numbers, of course!  I always enjoy seeing these creatures, because they unexpectedly pop up in the strangest problems.  There are a number of ways to define these numbers, one of which is to just write them out sequentially, starting with B_{0}:


1, -\frac{1}{2}, \frac{1}{6}, 0, -\frac{1}{30}, 0, \frac{1}{42}, 0, -\frac{1}{30}, 0, \dots


But in this case it is not so easy to guess the next value.  The clever reader will notice that all of the odd numbered Bernoulli numbers (except the first) are zero, but other than that there does not seem to be a clear pattern.  Fortunately, we can construct a function which generates the values as coefficients; we’ll call this function (surprise!) a generating function.


Definition.  We define the sequence \{B_{j}\}_{j=0}^{\infty} by

\displaystyle \frac{t}{e^{t} - 1} = \sum_{j=0}^{\infty}B_{j}\frac{t^j}{j!}.


Notice that this will, in fact, generate the B_{j} as coefficients times \frac{1}{j!}.  Neat.  In practice, you can use a program like Mathematica to compute B_{j} for pretty large values of j; but, of course, there are lists available.  We can now use Faulhaber’s formula above, which gives us (assuming we have proven that the formula holds!) that the sums of powers of natural numbers form polynomials of degree \alpha + 1.


But something else happens that’s pretty interesting.  Let’s look at some of the functions.


\begin{array}{|c|c|}\hline \alpha & \mbox{Polynomial}\\\hline &\\ 1 & \frac{1}{2}n^{2} + \frac{1}{2}n\\ &\\ 2 & \frac{1}{3}n^{3} + \frac{1}{2}n^{2} + \frac{1}{6}n\\ & \\ 3 & \frac{1}{4}n^{4} + \frac{1}{2}n^{3} + \frac{1}{4}n^{2} \\ & \\ 4 & \frac{1}{5}n^{5} + \frac{1}{2}n^{4} + \frac{1}{3}n^{3} - \frac{1}{30}n\\ & \\ \hline \end{array}


Look at the coefficients in each of these polynomials.  Anything strange about them?  Consider them for a bit.


Problem.  Look at the coefficients.  What do you find interesting about them?  Note that, in particular, for a fixed \alpha, the coefficients of the associated polynomial sum to 1.  Convince yourself that this is probably true (do some examples!) and then prove that it is true.  Do this before reading the statements below.


Anecdote.  I spent quite a while trying to write down the "general form" of a polynomial with elementary symmetric polynomials and roots to try to see if I could prove this fact using some complex analysis and a lot of terms canceling out.  This morning, I went into the office of the professor to ask him about what it means that these coefficients sum up to 1.  He then gave me a one-line (maybe a half-line) proof of why this is the case. 


Hint.  What value would we plug in to a polynomial to find the sum of the coefficients?  What does plugging in this value mean in terms of the sum?


This post was inspired by a question on the comment second of my last post about the prime-ness of 111…111.  The question is: what’s the sum of 1 + 11 + 111 + … + 111…111?  This seemed kind of silly to me (especially if the sum has less than 10 terms) but I quickly realized that I couldn’t figure out a "closed form" without appealing to weird "carry" tricks.  So I tried to figure something else out. 

Because my final solution to this question was somewhat unsatisfying, I’ve made this a special kind of post!  This post will have two main purposes: to try to answer this question and to show what kinds of things I do when I don’t know the answer to a problem.  So let’s begin.


First, I scribbled out lots of examples to see if there were patterns in the numbers.  Indeed, there are, but there was no nice way to describe them in general without creating a whole lot of variables and expanding the number of terms out into a base-ten sum.  This was frustrating.  Especially because I knew there might be an easy answer looming out there that I wasn’t clever enough to see. 

Second, I noted that 11 and 111 and 1111 are kind of weird numbers; written in base 10 they look pretty, but they don’t have much else in common.  As we saw in the last post, a few are prime but many are not, and many have very strange prime factorizations — these factorizations do group together, but that seemed to be too far away from this problem to use.  So, maybe another base would make them better formed?  I plugged away in wolfram alpha.  The first two bases I tried were base 2 and base 11.  Neither one worked nicely.  When I tried base 5, I found that the numbers followed an interesting pattern:

1, 11, 111, 1111, 11111, 111111, \dots

were mapped to

1, 21, 421, 13421, 323421, 12023421, \dots

Note that the last few digital always stay the same here.  Because the decimal form of these numbers is 1 + 10 + 100 + 10000 + … this is not all that surprising.  We’re essentially adding the base-5 versions of these together.  Note that 400_{5} means the number 400 in base 5; in decimal this is the number 100.  So 400_{5} = 100_{10}.  We drop the _{10} in our base 10 numbers and note the following:

1 = 1_{5}

10 = 20_{5}

100 = 400_{5}

1000 = 13000_{5}

10000 = 310000_{5}

100000 = 11200000_{5}

and while this seems to have a bit of a pattern, it grows too fast to be of use for adding.  On the other hand, I found that base 5 can be fairly neat when you input numbers that have "nice forms" in base 10.  Try it out!


Third, I was a bit upset, so I went back to thinking that I could write the number of terms as n = a_{0} + a_{1}10 + a_{2}10^{2} + \dots + a_{k}10^{k} and some some mods to figure out the digits.  The first digit will be easy: it’s just a_{0}.  But then what’s the carry?  After a bit, I worked out that it will just be \frac{n - a_{0}}{10}.  This did not seem to be going anywhere, since this number might be somewhat large too; we would need to add this number n - 1 times, and then there’s another carry that will look significantly more complex than the one I just wrote.  After trying this for five carries, I started to lose track of what I was doing; the formula was getting much more difficult than just doing "normal" addition.  This clearly wasn’t going to go anywhere.  At this point, a flash of insight hit me.  Of course.  This is just like adding 1 + 10 + 100 + 1000 + …, but only a little bit off.  But how much off? 


Fourth, I thought that, okay, 1 + 11 + 111 + 1111 +… is the same sum as 1 + 10 + 100 + 1000 + … with a difference of exactly 1 + 11 + 111 + … with one less term.  If there are n terms in the original, then it is equal to 1 + 10 + 100 + 1000 + \dots with n terms plus 1 + 11 + 111 + \dots with n -1 terms.  Note, then, that if we define the term ONE_{k} to be the sum of k terms that look like 1 + 11 + 111 + 1111\dots, then we have ONE_{k} = 111\dots 111 + ONE_{k-1}.  At this point, I began kicking myself, because this tells me nothing new about the problem; in fact, it is essentially a restatement of the problem!  But because of this, I thought about what happens when we do addition in 10’s.  I realized that it is exactly the same sort of thing we are doing when we add 11’s, but each successive digit will raise by 1.  So for example, while

1 + 10 + 100 + 1000 + 10000 = 11111

we have

1 + 11 + 111 + 1111 + 11111 = 12345


Each digit, starting at the left, is one plus the one before it.  Of course, this suggests a pattern.  But then what happens when you get far enough along? 


1 + 11 + 111 + 11111 + \dots + 111111111111 = 123456790122


which does not look as pretty.  But look; if we add in the following way, this becomes easy!  (I’ve attempted to use a chart to display place values.)


1 2 3 4 5 6 7 8 9      
                1 0    
                  1 1  
                    1 2
1 2 3 4 5 6 7 9 0 1 1 2


Which is exactly what we got above!  Note here that I’ve made a "10" that sits inside the tenth decimal place (and so is implicitly a carry of 1 in the ninth place) and a "11" that sits in the tenth place (and so is a carry of 1 in the tenth place and 1 in the eleventh place) and so on.  I’ve found that this method of computing is slightly faster than computing the original sum by hand and much less space consuming.  Unfortunately, the clever (and even not-so-clever) reader will notice that this is still the sum of n - 8 terms.  Though I find it faster because you are only adding at most three things in each column (carries included).  I tried to speed-test myself by adding together 20 terms this way and by doing 1 + 11 + 111 + … etc. straight out.  My times are as follows:


Original Way (Adding 1 + 11 + 111…): 1 minute. 

New Way (Described above): 40 seconds.


I also was much less confident doing this the original way (try it; you’ll have to keep track of the carry and the number of ones you need to add up and that gets confusing).  The most time consuming part about the "new way" was writing out the problem; I did not count this in the "original way" because it’s just as easy to visualize the problem as it is to write it out — it would take significantly longer.  If I were to only time the "calculation" part, the new way took me about 15 seconds.  Pretty good for a human.


But, this solution was the best I could do.  I do not have a closed form.  If anyone has a different or more interesting solution, let me know.  I didn’t want to resort to asking google, but maybe there’s a cute trick that makes this into a nice closed form.  I’m not sure.


Edit: Of course, there is an easier solution which was provided to me by Josh "The Widowmaker" Silverman over at his blog.  The key was to represent this as a geometric series (something that I seem to have completely missed out on).  It turns out that the closed form expression is

\frac{1}{81}(10^{n+1} - 10 - 9n)

for the sum of the first n numbers of this form.  To see the derivation, go to his blog and read it over.

When you’re on facebook, you’ll see a lot of people posting a lot of silly things.  It would be interesting to see what kinds of things are posted when, but this is a subject for some kind of cybersociologists.  Nonetheless, if you are awake at around 11pm and on facebook (and, I’ll admit it, I’m one of these people), you might see a string of comments that essentially say: "omg, it’s 11:11, make a wish."

If you’re superstitious or obsessive compulsive, this might be a lucky reminder to make a wish at this time, but besides its symmetry and visually appealing form, what’s so special about 1111? 

Read the rest of this entry »