0
$\begingroup$

In complexity theory, it is sometimes necessary to find the "closed-form solution" of a summation.

This was put in our exam guide as "solving arithmetic and geometric series", which I initially understood as finding the nth term and the sum to n of a series.

I now understand that it refers to finding the closed-form solution of the sum and I know that the formulae for these three things are different.

What is the relation between finding the nth term and the sum, and finding the closed-form solution, if any?

$\endgroup$
1
$\begingroup$

It is easiest to see the differences using an example, so consider the geometric series $\sum_{k=1}^{j}{ar^{k-1}}$ with initial value $a$ and common ratio $r$.

To find the nth term evaluate the summand $ar^{k-1}$ when $k = n$.

1st term = $ar^{1-1} = ar^0 = a$

2nd term = $ar^{2-1} = ar^1 = ar$

(n-1)th term = $ar^{(n-1)-1} = ar^{n-2}$

nth term = $ar^{n-1}$

To find the closed form, rewrite the sum so that it does not contain a summation. Essentially, it is a formula for the sum of the first j terms of the summation which can be evaluated in one step, instead of j steps. We do this by factoring out the initial value then multiplying both sides by $(r - 1)$ which will cancel all but the last term.

$\sum_{k=1}^{j}{ar^{k-1}} = a + ar + ar^2 + \dots + ar^{j-2} + ar^{j-1}$

$\sum_{k=1}^{j}{ar^{k-1}} = a(1 + r + r^2 + \dots + r^{j-2} + r^{j-1})$

$(r -1)\sum_{k=1}^{j}{ar^{k-1}} = a(r - 1)(1 + r + r^2 + \dots + r^{j-2} + r^{j-1})$

$(r - 1)\sum_{k=1}^{j}{ar^{k-1}} = a(r + r^2 + r^3 + \dots + r^{j-1} + r^{j} - 1 - r - r^2 - \dots - r^{j-2} - r^{j-1})$

$(r - 1)\sum_{k=1}^{j}{ar^{k-1}} = a(r^{j} - 1)$

$\sum_{k=1}^{j}{ar^{k-1}} = a\frac{r^{j} - 1}{r - 1}$

So $a\frac{r^{j} - 1}{r - 1}$ is the closed form of the geometric series.

Finally, we can find the sum of the first j terms using either the summation or its closed form and get the same answer, e.g. for $a = 3, r = \frac{1}{2}, j = 4$:

$\sum_{k=1}^{4}{3\left(\frac{1}{2}\right)^{k-1}} = 3 + 3\left(\frac{1}{2}\right) + 3\left(\frac{1}{4}\right) + 3\left(\frac{1}{8}\right) = 3\left(\frac{15}{8}\right)$

$3\left(\frac{\left(\frac{1}{2}\right)^{4} - 1}{\frac{1}{2} - 1}\right) = 3\left(\frac{\frac{1}{16} - 1}{-\frac{1}{2}}\right) = 3\left(\frac{-\frac{15}{16}}{-\frac{8}{16}}\right) = 3\left(\frac{15}{8}\right)$

$\endgroup$
  • $\begingroup$ Thanks! So are they just different ways of achieving the same goal? $\endgroup$ – Jacob May 23 '15 at 17:46
  • 1
    $\begingroup$ To find the sum you must either evaluate the summation or its (equivalent) closed form. Evaluating a closed form is simple -- just plug in numbers and directly compute the result. Evaluating a summation requires you to evaluate each individual nth term and add them up. So that is how they relate to each other, i.e. closed form and summations achieve the same goal. $\endgroup$ – affinehat May 24 '15 at 22:19

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.