Wednesday, August 23, 2017

Solution to simple recursive series












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$


Answer



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


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...