1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thank you, accepted your answer because it was first and a bit more simple to follow. I guess for all of these questions, in general, I need to determine the type of series then google for identities? $\endgroup$ – Austin Feb 5 '16 at 20:57
  • 1
    $\begingroup$ No. You need to learn how to derive the results by yourself. If you can't, get help. $\endgroup$ – marty cohen Feb 5 '16 at 21:50
4
$\begingroup$

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.

enter image description here

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}$.

$\endgroup$
2
$\begingroup$

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}$$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.