A Beautiful Sum: Σ k · 2ᵏ

The other day I came across a post on Stack Overflow that asked for help working out a summation. As an intermediary step, I needed to evaluate the sum \sum_{k=0}^n k \cdot 2^k. This wasn’t a sum I’d seen before, and some quick Googling didn’t turn anything up. I managed to find this Wikipedia entry on arithmetico-geometric series, which gave me a closed-form, but I wasn’t very satisfied with having to look it up, especially given that the resulting formula was pretty messy.

When I was lying in bed that evening I realized that there was a beautiful connection between this sum and another one I’d seen, and that suggested a route for solving it. This morning I got up, put some animated slides together, and uploaded my very first YouTube video!

I think this is a beautiful derivation and love the multiple uses of sums of powers of two.

I’m thinking there’s almost certainly another route to solving this summation that routes through finite calculus. The sum is analogous to \int{x \cdot e^x dx}, given that the functions e^x and 2^x play similar roles in traditional and finite calculus as fixed points of the derivative operator. You can use integration by parts to show that \int{x \cdot e^x dx} = (x - 1)e^x + C, which works out pretty similarly to the resulting (n-2)\cdot 2^n + 2 that you get from the discrete sum. I think the extra “nudges” here are an artifact of the shift operator that shows up in finite calculus’ version of integration by parts, but I haven’t chased the details down yet.

In the meantime, I hope that if someone else in the future is looking for how to work out this sum, this saves you a lot of time and gives you a perspective on where the result comes from!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s