Commenter Rachel recently asked,

How would you find the sum of ?

See here for an explanation of sigma notation—in this case it denotes the sum

Of course, for any particular value of we can just plug in values and do a bunch of adding. But I interpret Rachel’s question to mean “can we find an algebraic expression in terms of which lets us compute the sum more quickly than actually adding the individual terms?”

Let’s try!

First, we observe that

Why? If you think about it a bit, you can see that the same terms show up on the left and the right, just in a different order: the left side is whereas the right side is . Since addition is associative () and commutative () these are equal.

Next, we observe that

,

that is, . This is because multiplication distributes over addition.

So, we have .

is just copies of , so it is equal to . I’ve written before about ; it is equal to . So far, we have

.

What about that pesky ? Can it be simplified at all?

It can, and I know of a few different ways to figure it out. I’ll show you one of them today (and hopefully others in the future).

Consider the sum

For example, if we have . Notice that we end up with both and , and … in fact, everything cancels except the at the beginning and the at the end. I hope you can see that in general,

This sort of sum is called a “telescoping” sum, because the whole thing “collapses” like one of those old-school telescopes that pirates use.

However, we can also expand out the and then simplify:

So now we know that

since both sides are equal to . From here we just need some algebra to put on one side and everything else on the other, and clean things up a bit to obtain… well, I’ll let you finish working it out. =)

Thank you so much!!! Very thorough!! You are a lifesaver

I prefer writing the sum in terms of binomial coefficients because .

Since , then .

We can conclude that , which can be expanded if desired.

Aha, very clever! I will have to remember this technique — expressing polynomials using binomial coefficients as a basis. Actually, now that I think about it, this is essentially the same as using a basis involving falling powers (like ) which allows one to do

discrete calculus(which I learned from Graham, Knuth and Patashnik’sConcrete Mathematics). I just hadn’t remembered the connection to binomial coefficients. I hope to write about it in a future post.All Korean high school students must recite and memorize compulsorily these formulas

to solve every sum of polynomial whose degree is less than 4.as fast as possible.

Thus, most of Korean high school student will solve this problem like this :

This solution is not fun. I like yours. :)

Yes, I happen to have these memorized too, but only because I’ve seen them enough times. I was just trying to show how you would actually come up with these formulas in the first place!

And every Chinese schoolboy knows that if you give a man a fish, you’ve fed him for a day. But if you teach him how to fish, you’ve fed him for a lifetime.