Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question

marked as duplicate by Marvis, Ross Millikan, Martin Sleziak, Ayman Hourieh, Zev Chonoles Jun 17 '12 at 16:04

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
$a_1 = C a_0$, $a_2 = Ca_1 = C^2 a_0$, $a_3 = Ca_2 = C^3 a_0$ and in general $a_n = C^n a_0$. Hence, $$\sum_{k=0}^{n} a_k = \sum_{k=0}^{n} \left(a_0C^k \right) = \underbrace{a_0 \left( \sum_{k=0}^{n} C^k\right) = a_0 \left(\dfrac{C^{n+1}-1}{C-1} \right)}_{\text{Sum of a geometric progression when $C \neq 1$}}$$ If $C=1$, you get $\displaystyle \sum_{k=0}^{n} a_k = \displaystyle \sum_{k=0}^{n} a_0 = (n+1)a_0$. You can find on how to evaluate a geometric progression in the link below. (math.stackexchange.com/questions/29023) –  user17762 Jun 16 '12 at 19:29
    
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. –  Ross Millikan Jun 16 '12 at 19:40
add comment

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
Thanks a lot, I had a feeling it wasn't that complex after all –  jimmyjambles Jun 17 '12 at 3:47
add comment

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