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?”
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’s Concrete 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.