Closed-form Solution to a Sum

Question

I have some math questions for a programming course where it says to provide closed-form solutions for a list of sums. I've never taken an algorithms course, so I'm not quite sure what I'm doing. I wiki'ed closed-form and I think I get it, but what's the procedure for actually solving for the closed-form solution? For example: $$\sum_{i=0}^{\infty} \frac{1}{3^i}$$ I was looking up different kinds of sums and I think this might be called a geometric series, does that help me at all? I think the limit as $i \rightarrow \infty = 0$, but don't know if that's useful either.

Answer 1

Yup, this is a geometric series.

$$1 + \frac{1}{3} + \frac{1}{9} + \frac{1}{27} + \dots$$

The terms get arbitrarily small, so they do indeed go to zero as $i \rightarrow \infty$. But the sum definitely isn't $0$, since it's the sum of a bunch of positive numbers.

There's a lot to explore here. I found a nice link with some good pictures -- scroll down for a while and it'll get to your series.

This picture (from that site) is of a square being cut into thirds, with the left colored purple and the right colored orange, then the process repeated again with the middle third. (This is if we start the sum at $1/3$ instead of $1$). The idea is that it's a way to see that the sum:

$$1 + \frac{1}{3} + \frac{1}{9} + \frac{1}{27} + \dots = \frac{3}{2}$$

We can find this algebraically: assuming such a sum exists, call it $S$.

$$ \begin{aligned} 1 + \frac{1}{3} + \frac{1}{9} + \frac{1}{27} + \dots &= S\\ 3(1 + \frac{1}{3} + \frac{1}{9} + \frac{1}{27} + \dots) &= 3S\\ 3 + 3(\frac{1}{3} + \frac{1}{9} + \frac{1}{27} + \dots) &= 3S\\ 3 + (1 + \frac{1}{3} + \frac{1}{9} + \dots) &= 3S\\ 3 + S &= 3S\\ \frac{3}{2} &= S\\ \end{aligned} $$

Try doing the above yourself, but for an arbitrary $n$ in $\sum_{i=0}^\infty \frac{1}{n^i}$.

Answer 2

Indeed it is the sum of a geometric series. Have you seen that $S=\sum_{i=0}^{\infty} x^i= \dfrac {1}{1-x}$ provided that $|x|<1$ ? Then take $x=1/3$. The result is $S=3/2$.

Answer 3

Notice, use the following identities:

• $$\sum_{n=q}^{m}\frac{b}{a^n}=\frac{b\left(\frac{1}{a^m}-a^{1-q}\right)}{1-a}$$
• $$\sum_{n=q}^{\infty}\frac{b}{a^n}=\frac{ba^{1-q}}{a-1}\space\text{when}\space|a|>1$$

And, you can use the geometric series test to proof that this series converges!

---

Set $m\to\infty$ and $n=0,b=1,a=3$:

$$\lim_{m\to\infty}\sum_{n=0}^{m}\frac{1}{3^n}=\lim_{m\to\infty}\frac{1\left(\frac{1}{3^m}-3^{1-0}\right)}{1-3}=$$ $$\lim_{m\to\infty}\frac{\frac{1}{3^m}-3}{-2}=-\frac{1}{2}\lim_{m\to\infty}\left[\frac{1}{3^m}-3\right]=$$ $$-\frac{1}{2}\left[\lim_{m\to\infty}\frac{1}{3^m}-3\right]=-\frac{1}{2}\left[0-3\right]=\frac{3}{2}$$

Answer 4

You are correct that this is an example of a geometric series! A closed form solution of a summation, generally speaking, is a way of representing it which does not rely on a limit or infinite sum.

So for example, if $x\in \mathbb{R}$, and $x>0$, we can find a closed form for the infinite sum $\sum_{i=0}^{\infty}\frac{1}{x^i}$ as follows:

\begin{align*} \sum_{i=0}^{\infty}\frac{1}{x^i}&=\lim_{n\rightarrow \infty}\sum_{i=0}^{n}\frac{1}{x^i}\\ &=\lim_{n\rightarrow \infty}\bigg(\Big(\frac{1}{x}\Big)^0+\Big(\frac{1}{x}\Big)^1+...+\Big(\frac{1}{x}\Big)^n\bigg)\\ &=\lim_{n\rightarrow \infty}\bigg(\frac{1-\big(\frac{1}{x}\big)^{n+1}}{1-\big(\frac{1}{x}\big)}\bigg) &&\text{this can be confirmed by long division.}\\ &=\frac{1}{1-\frac{1}{x}} &&\text{Since $x^{n+1}$ gets arbitrarily large.}\\ \end{align*} This is a closed form for the sum, in particular, when you replace $x$ with 3, it is the sum in your question.

Answer 5

An infinite geometric series can be written as $S=ar^0+ar^1+ar^2+...$, where $a=1$ in your case, and $r$ is the ratio of two consecutive terms ($\frac{1}{3}$ in your case). If $|r|<1$ then the series converges and the formula for what it sums to is $S=\frac{a}{1-r}$, which in your case would be $\frac{3}{2}$.