At math competitions, I often see a problem along the lines of "Let . Find " and notice that not that many people are able to solve it (the answer is ). I'm going to show how to solve that kind of problem in this note.
The first thing we need to do is to find the value of for some We can solve this with some clever manipulation and summation of geometric series. Recall that for
We can see that each line we have created is a summable geometric series. Let's see what happens when we sum each line. Let
We can notice two things from this. First, our original problem can be rewritten as finding Also, This means that is a geometric series.
So what does this mean for our original problem? After all, this only gives us a way to find not Fortunately, we can make that leap with some nice index shifting.
First - what is index shifting? Index shifting is the technique of saying that For example, Now let's find a general formula for to demonstrate how we can apply this technique.
That last step may seem a little strange, but take a look at what happens when in each sum.
In the first two sums, the term has a numerator of meaning that the term is equal to Thus, we can get rid of it and start the sum at the term. In the third sum, the term is not equal to we can just index shift the out.
We have simplified the problem enough to solve for .
You can use similar techniques to find higher order sums, though problems going past are trolls.
Here is a helpful list for sums of order
It should be noted that where is the th Eulerian polynomial.
I hope this helped you out! Best of luck solving these kinds of problems!