Waste less time on Facebook — follow Brilliant.

A Special Summation Problem

At math competitions, I often see a problem along the lines of "Let \(S=\displaystyle\sum_{n=1}^\infty\dfrac{n^2}{2^n}\). Find \(S.\)" and notice that not that many people are able to solve it (the answer is \(6\)). 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 \(\displaystyle\sum_{n=1}^\infty\dfrac{n}{k^n}\) for some \(|k|>1.\) We can solve this with some clever manipulation and summation of geometric series. Recall that \(\displaystyle\sum_{n=0}^\infty ab^n=\dfrac{a}{1-b}\) for \(|b|<1.\)

\[ \begin{align*} \displaystyle\sum_{n=1}^\infty\dfrac{n}{k^n}=\dfrac{1}{k}+\dfrac{2}{k^2}+\dfrac{3}{k^3}+\dfrac{4}{k^4}+&\ldots\\ =\dfrac{1}{k}+\dfrac{1}{k^2}+\dfrac{1}{k^3}+\dfrac{1}{k^4}+&\ldots\\ +\dfrac{1}{k^2}+\dfrac{1}{k^3}+\dfrac{1}{k^4}+&\ldots\\ +\dfrac{1}{k^3}+\dfrac{1}{k^4}+&\ldots\\ +\dfrac{1}{k^4}+&\ldots\\ &\ddots \end{align*} \] 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 \(s_x=\displaystyle\sum_{n=x}^\infty\dfrac{1}{k^n}.\) \[ \begin{align*} s_1=\dfrac{1}{k}+\dfrac{1}{k^2}+\dfrac{1}{k^3}+\dfrac{1}{k^4}+\ldots&=\sum_{n=1}^\infty\dfrac{1}{k^n}=\dfrac{\frac{1}{k}}{1-\frac{1}{k}}=\dfrac{1}{k-1}\\ s_2=\dfrac{1}{k^2}+\dfrac{1}{k^3}+\dfrac{1}{k^4}+\ldots&=\sum_{n=2}^\infty\dfrac{1}{k^n}=\dfrac{\frac{1}{k^2}}{1-\frac{1}{k}}=\dfrac{1}{k^2-k}\\ s_3=\dfrac{1}{k^3}+\dfrac{1}{k^4}+\ldots&=\sum_{n=3}^\infty\dfrac{1}{k^n}=\dfrac{\frac{1}{k^3}}{1-\frac{1}{k}}=\dfrac{1}{k^3-k^2}\\ s_4=\dfrac{1}{k^4}+\ldots&=\sum_{n=4}^\infty\dfrac{1}{k^n}=\dfrac{\frac{1}{k^4}}{1-\frac{1}{k}}=\dfrac{1}{k^4-k^3}\\ &\vdots \end{align*} \]

We can notice two things from this. First, our original problem can be rewritten as finding \(\displaystyle\sum_{x=1}^\infty s_x.\) Also, \(s_{x+1}=\dfrac{s_x}{k}.\) This means that \(\{s_1, s_2, s_3\ldots\}\) is a geometric series. \[ \begin{align*} \sum_{x=1}^\infty s_x&=s_1+s_2+s_3+\ldots\\ &=\dfrac{1}{k-1}+\dfrac{1}{k^2-k}+\dfrac{1}{k^3-k^2}+\ldots\\ &=\dfrac{\frac{1}{k-1}}{1-\frac{1}{k}}\\ &=\dfrac{k}{(k-1)^2} \end{align*} \]

So what does this mean for our original problem? After all, this only gives us a way to find \(\displaystyle\sum_{n=1}^\infty\dfrac{n}{2^n},\) not \(\displaystyle\sum_{n=1}^\infty\dfrac{n^2}{2^n}.\) Fortunately, we can make that leap with some nice index shifting.

First - what is index shifting? Index shifting is the technique of saying that \(\displaystyle\sum_{i=a}^bx_i=\displaystyle\sum_{i=a-c}^{b-c}x_{i+c}.\) For example, \(\displaystyle\sum_{i=1}^\infty\dfrac{1}{2^i}=\displaystyle\sum_{i=0}^\infty\dfrac{1}{2^{i+1}}.\) Now let's find a general formula for \(S=\displaystyle\sum_{n=1}^\infty\dfrac{n^2}{k^n}\) to demonstrate how we can apply this technique.

\[ \begin{align*} \displaystyle\sum_{n=1}^\infty\dfrac{n^2}{k^n}&=\displaystyle\sum_{n=0}^\infty\dfrac{(n+1)^2}{k^{n+1}}\\ &=\displaystyle\sum_{n=0}^\infty\dfrac{n^2}{k^{n+1}}+\displaystyle\sum_{n=0}^\infty\dfrac{2n}{k^{n+1}}+\displaystyle\sum_{n=0}^\infty\dfrac{1}{k^{n+1}}\\ &=\displaystyle\sum_{n=1}^\infty\dfrac{n^2}{k^{n+1}}+\displaystyle\sum_{n=1}^\infty\dfrac{2n}{k^{n+1}}+\displaystyle\sum_{n=1}^\infty\dfrac{1}{k^n}\\ \end{align*} \] That last step may seem a little strange, but take a look at what happens when \(n=0\) in each sum.

In the first two sums, the \(n=0\) term has a numerator of \(0,\) meaning that the \(n=0\) term is equal to \(0.\) Thus, we can get rid of it and start the sum at the \(n=1\) term. In the third sum, the \(n=0\) term is not equal to \(0,\) we can just index shift the \(n=0\) out.

\[ \begin{align*} \displaystyle\sum_{n=1}^\infty\dfrac{n^2}{k^{n+1}}+\displaystyle\sum_{n=1}^\infty\dfrac{2n}{k^{n+1}}+\displaystyle\sum_{n=1}^\infty\dfrac{1}{k^n}&=\dfrac{1}{k}\displaystyle\sum_{n=1}^\infty\dfrac{n^2}{k^n}+\dfrac{2}{k}\displaystyle\sum_{n=1}^\infty\dfrac{n}{k^n}+\displaystyle\sum_{n=1}^\infty\dfrac{1}{k^n} \end{align*} \] We have simplified the problem enough to solve for \(S\). \[ \begin{align*} S&=\dfrac{S}{k}+\dfrac{2}{k}\times\dfrac{k}{(k-1)^2}+\dfrac{1}{k-1}\\ S\left(\dfrac{k-1}{k}\right)&=\dfrac{2}{(k-1)^2}+\dfrac{k-1}{(k-1)^2}\\ &=\dfrac{k+1}{(k-1)^2}\\ S&=\dfrac{k(k+1)}{(k-1)^3} \end{align*} \] You can use similar techniques to find higher order sums, though problems going past \(\displaystyle\sum_{n=1}^\infty\dfrac{n^4}{k^n}\) are trolls.

Here is a helpful list for sums of order \(\leq6\)

\[ \begin{align*} \sum_{n=1}^\infty\dfrac{1}{k^n}&=\dfrac{1}{k-1}\\ \sum_{n=1}^\infty\dfrac{n}{k^n}&=\dfrac{k}{(k-1)^2}\\ \sum_{n=1}^\infty\dfrac{n^2}{k^n}&=\dfrac{k(k+1)}{(k-1)^3}\\ \sum_{n=1}^\infty\dfrac{n^3}{k^n}&=\dfrac{k\left(k^2+4k+1\right)}{(k-1)^4}\\ \sum_{n=1}^\infty\dfrac{n^4}{k^n}&=\dfrac{k\left(k^3+11k^2+11k+1\right)}{(k-1)^5}\\ \sum_{n=1}^\infty\dfrac{n^5}{k^n}&=\dfrac{k\left(k^4+26k^3+66k^2+26k+1\right)}{(k-1)^6}\\ \sum_{n=1}^\infty\dfrac{n^6}{k^n}&=\dfrac{k\left(k^5+57k^4+302k^3+302k^2+57k+1\right)}{(k-1)^7}\\ \end{align*} \] It should be noted that \(\displaystyle\sum_{n=1}^\infty\dfrac{n^x}{k^n}=\dfrac{kA_n(k)}{(k-1)^{x+1}}\) where \(A_n(k)\) is the \(n\)th Eulerian polynomial.

I hope this helped you out! Best of luck solving these kinds of problems!

Note by Trevor B.
1 year, 7 months ago

No vote yet
1 vote


Sort by:

Top Newest

Check this PolyLogarithm Ronak Agarwal · 1 year, 7 months ago

Log in to reply

Thanks!!!!!! Akshat Sharda · 1 year, 2 months ago

Log in to reply

Thanks a lot for the note. It helped a lot. Vishwak Srinivasan · 1 year, 3 months ago

Log in to reply

These questions are what I call Arithmetic Geometric Progression. I started a wiki page on it, but it is still a work in progress. Help would be appreciated! Calvin Lin Staff · 1 year, 7 months ago

Log in to reply

@Calvin Lin @Trevor B. We've made several edits to the Arithmetic-Geometric Progression wiki page. Can you look over it and see if there are any improvements? Calvin Lin Staff · 1 year, 2 months ago

Log in to reply

Amazing Man !!! Rajdeep Dhingra · 1 year, 7 months ago

Log in to reply

Very nice note! Trevor Arashiro · 1 year, 7 months ago

Log in to reply

Nice algebraic method; I mostly use calculus for these sorts but this was an eye-opener. Jake Lai · 1 year, 7 months ago

Log in to reply

That's simply Brilliant , Trevor Azhaghu Roopesh M · 1 year, 7 months ago

Log in to reply

@Azhaghu Roopesh M Thanks @Azhaghu Roopesh M! I'm glad it helps. Trevor B. · 1 year, 7 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...