# An elegant analysis of a summation…

Today, I’ve prepared myself to expound a math problem. And yeah, this is the first time I’m introducing math into my blog. Before we get into that, you gotta believe me that I’m no “big guy” in math. I have some unsaturated background in math, which (as far as I know) is good enough to “understand” my amateur Physics (quite satisfactorily). If Physics is sorcery, then math is um, totally wicked. Both are fun and exceedingly enjoyable. Well usually, I don’t spend much of my brain-time dwelling inside math, but I do often go around and read posts written by others.

Every month, one or two posts loom into the crowd and attracts my mind in some way. Within hours, they become a vote-magnet. I’m way too sure that that’s due to the modesty of the answerer, especially the elegance of the solution he has brought upfront. So, I thought I could selectively bring those here, where I can write a bit more about it. No, I’m not just copy-pasting stuff. Like I said, I’ll blog about those, only if I feel like having some of my own enhancements to the existing solution.

So, math posts are gonna be a part of my future posts. Don’t worry, they won’t be complicated at all. They’d be very easy, just like the squeeze of a toothpaste. And mind you, there exist numerous solutions to a specific problem, because it’s math. It’s crazy. But like I said, these are somewhat attractive, in the sense that an elegant generalization comes out at last.

Today, we’re gonna analyze the convergence of a specific power series…

## The series of powers over “powers-of-two”

Um, I just “phrased” the series below…

$\displaystyle \sum_{n=0}^\infty \frac{n^2}{2^n}$.

Where does this series converge? Careful analysis, or a plot of the function gives you the value 6 (well, the latter is quite harmless, in my opinion). If you’re a beginner to this (I hope not), then you might wonder what this “convergence” means? Never mind, it’s worth taking a look on that.

You take any simple infinite series, it either converges to a certain value or diverges to infinity (while there are other complicated ones, which neither converge nor diverge, but those aren’t necessary). Say, you add the terms one by one in the series. As the number of terms increases, either the series goes towards a specific limit (beyond which it can’t further increase) or it goes towards infinity. I can give examples simply by using the above series…

Case (i): Taking the numerator alone – $\displaystyle \sum_{n=0}^\infty n^2$

You can easily declare that it’s a divergent series, because once you start adding the terms one by one as $1+4+9+16+25+...$, you can easily notice that it reaches infinity.

Case (ii): Now, applying the same tactics to the denominator – $\displaystyle \sum_{n=0}^\infty \frac{1}{2^n}$

Bad luck, it’s become convergent. As you add the terms like $0.5+0.25+0.125+0.0625+...$, you’ll notice something weird. It goes nearer and nearer to 2, but never really touches 2. But, as I’m also aware that the series never goes beyond 2 in its lifetime, I can safely declare that it’s a convergent series.

The specialty of this convergence & divergence of an infinite series is that I can directly replace them with the values of the series in complicated problems. For instance, if the second case comes in a problem, instead of writing the whole expression, I can simply write the value of the series, which is 2. It’s also worth stating that there are a number of ways to test the convergence, like root test, ratio test, etc.

## It’s time to analyze the series…

We know the value of the series in the second case, which is 2. Let’s give a name for that, as naming becomes handy for later steps.

$\displaystyle A := \sum_{n=0}^\infty \frac{1}{2^n} = 2$

Note the use of “:=” in the expression. It means that instead of writing the whole expression in the future steps of our analysis, I can simply write $A$. Now, I’ll synonymize the original series as $C$.

$\displaystyle C := \sum_{n=0}^\infty \frac{n^2}{2^n}$

What’s the first term in the series? That’s easy, zero (well, substitute $n=0$ in the expression). So, let’s neglect the term. Rewriting the series (changing the variable name) and taking the twice on both sides,

$\displaystyle C := \sum_{m=1}^\infty \frac{m^2}{2^m} \implies 2C = \sum_{m=1}^\infty \frac{m^2}{2^{m-1}}$

Firstly, there’s nothing wrong in changing the variable name (I just wrote $n$ as $m$). And second, note that the series now starts from $m=1$ because we’ve just neglected the first term. Now, let’s apply the transformation $n=(m-1)$ for which the expression becomes,

$\displaystyle 2C = \sum_{n=0}^\infty \frac{(n+1)^2}{2^n} = \sum_{n=0}^\infty \frac{(n^2+2n+1)}{2^n}$

Let’s subtract the original $C$ and thereby obtain,

$\displaystyle 2C-C=\sum_{n=0}^\infty \frac{(n^2+2n+1)}{2^n}-\sum_{n=0}^\infty \frac{n^2}{2^n}$

So, we’ve shown that $\displaystyle C=\sum_{n=0}^\infty \frac{(2n+1)}{2^n}$ which can be split into $\displaystyle \sum_{n=0}^\infty \frac{2n}{2^n} + A$. Hopefully, we know that $A=2$ (well, recall our second case, where we concluded that the series converged at 2). By that, we’re left out with the first series. Since the first term is zero in that series too, we can happily apply the same trick and legitimize the expression, to satisfy ourselves.

Let $\displaystyle B:= \sum_{n=0}^\infty \frac{n}{2^n}$

I’ll skip to the last step, where you’ll get a really “convincing” result…

$\displaystyle 2B-B=\sum_{n=0}^\infty \frac{n+1}{2^n}-\sum_{n=0}^\infty \frac{n}{2^n}$

$\displaystyle \implies B=\sum_{n=0}^\infty \frac{1}{2^n}=A$ which is 2 again.

Armed with $A$ and  $B$, let’s find $C$, by substituting the results in our tricked expression, which gives

$C=2B+A=2(2)+2=6$

If you still need a proof to convince yourselves, then here’s the plot for $A$$B$ and $C$.

This is just a stepped plot, because I simply summed up the terms in the series while plotting. Since the terms are being added one by one, and each of which are having different values, the overall plot turns out to be an intermittent one. That explains why it’s ugly.

Here’s a nice rounded version if you want…

Anyways, you can see that they converge exactly at 2 and 6.

By that way, you can go on finding the further higher powers. But, it seems quite inefficient. To generalize our solution, let’s take one last higher power. Using the same trick, you’ll arrive at a similar result…

$\displaystyle 2D-D=\sum_{n=0}^\infty \frac{(n^3+3n^2+3n+1)}{2^n}-\sum_{n=0}^\infty \frac{n^3}{2^n}$

$D=3C+3B+A=3(6)+3(2)+2=26$

There’s something I want you to observe. So far, we’ve been using binomial expansion for every power of $n$. For every $(n+1)^m$, the first term (i.e) $n^m$ cancels out. The remaining binomial coefficients are still there. So, we can make use of Pascal’s triangle.

The rows of this triangle represent the power of the expansion starting from $n=0$, whereas individual cells represent the $i^{th}$ term in the series, starting with the highest power at any one of the ends of the row. The values of these cells can be obtained by two ways.

Either you write out the “One’s” in the triangle and add the values of the cells above, to obtain the value of the cell directly below. Or, you can use the formula…

$\biggl( \begin{matrix}n \\ i\end{matrix}\biggl)=$ $\frac{n!}{i!(n-i)!}$

That gives you the value of the $i^{th}$ cell of power $n$. By using the triangle, you can generate the relationship between $A,B,C,D$ in those expressions.

For example, let’s take our series, but with the fourth power. Now, we’ll be able to get the expression,

$E=4D+6C+4B+A=4(26)+6(6)+4(2)+2=150$

This method is still inefficient. Because, you need all the previous values to calculate the new values. For instance, take the above example. If you wanna find $E$, you need the values of $A$, $B$, $C$ & $D$.

But as far as I know, this is a lot more generalized than many other solutions I’ve seen…

Inspired by this answer written by a graduate student at Math Stack Exchange. Actually, it took me a while to understand that.