# Solution to simple recursive series [duplicate]

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$

-

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

$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

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

-
Thanks a lot, I had a feeling it wasn't that complex after all –  jimmyjambles Jun 17 '12 at 3:47