1
$\begingroup$

Possible Duplicate:
Proof of the formula $1+x+x^2+x^3+ \cdots +x^n =\frac{x^{n+1}-1}{x-1}$
Value of $\sum\limits_n x^n$

I'm working on some math programming and ran into the following recursive series.

$\displaystyle\sum\limits_{i=1}^n a_n$. Where $a_{n} = Ca_{n-1}$ and $0 \leq C \leq 1$ and $a_0$ is given;

Because my constant values are always between 0 and 1, I know that the series converges and I can't help but thinking that there must be a solution.

My code looks something like

value = 1000000; constant = 0.9999; total = 0; tolerance = 0.001;  while(value > tolerance) {     value = constant * value;     total = total + value; } 

Problem is, as is the case with the initial values provided in the snippet above, the algorithm takes a long time to complete when $C$ approaches $1$

  • 0
    Note that in your code you stop adding terms as soon as one term is smaller than tolerance. The total of all the terms after that to infinity is $\frac {tolerance}{1-C}$. If $C$ is close to $1$ this can be large. In your case, it would be 100.2012-06-16

1 Answers 1

1

$a_k$ can be written as:

$a_k = a_0 \cdot \underbrace{C \cdot C \cdots C}_{k \text{ times}} = a_0 C^{k}$

Where $a_0 = 1000000$ and $C = 0.9999$. ($0 \lt C \lt 1$)

The sum is a geometric series. It has the following closed form:

$ \sum_{k=0}^n a_k = a_0 \frac{1-C^{n+1}}{1-C} $

And as $n \to \infty$:

$ \sum_{n=0}^\infty a_n = \frac{C_0}{1-C} $

On the other hand, if $C=1$, then $a_k=a_0$ and the sum becomes:

$ \sum_{k=0}^n a_k = (n+1)a_k $

And this diverges as $n \to \infty$.

  • 0
    Thanks a lot, I had a feeling it wasn't that complex after all2012-06-17