1
$\begingroup$

Wolfram Alpha provides the following exact solution $$ \sum_{i=1}^N (1+k)^i = \frac{(1+k)\,((1+k)^N-1)}{k}.$$ I wish to solve for $N$ of the order of several thousand and $|k|$ very small (c. $10^{-12}).$ When I do this on a computer in excel the software cannot handle it (because of truncation of significant figures) and the results are nonsense.

I thought to approximate the result using the first few terms of a series in increasing powers of $k$. I can multiply out the first few terms and examine the patterns in the following pyramid... $$(1+k)^1 = k +1 $$ $$(1+k)^2 = k^2 +2k +1 $$ $$(1+k)^3 = k^3 +3k^2 +3k +1 $$ $$(1+k)^4 =k^4+4 k^3+6 k^2+4 k+1$$ $$(1+k)^5 =k^5+5 k^4+10 k^3+10 k^2+5 k+1$$ $$(1+k)^6 =k^6+6 k^5+15 k^4+20 k^3+15 k^2+6 k+1$$

So for example, for $N=3$ we would obtain the sum $$ S= k^3 +4k^2 +6k +1 $$

The results suggest a solution with a pattern of the form $$ S = a + bk^1 +ck^2+dk^3... $$

I can see that $a=N$. The other coefficients increase monotonously and it might be possible to determine a formula for the coefficients from the pattern. Although the general pattern is not convergent, it is possible that for certain restricted ranges of $N$ and $k$ a convergent formula could be obtained. If so then it is possible that a useful approximation of S can be obtained just by evaluating the first few terms in the series.

But is there a well-known general formula for the terms in this series or can one be derived algebraically from the original formula?


UPDATE

following on from the answer by User73985...

$$ S=\sum_{i=1}^N (1+k)^i = N + \sum_{j=2}^{N+1}\binom{N+1}{j}k^{j-1}$$ So $$ S= N + \sum_{j=2}^{N+1}\frac{(N+1)!}{(N+1-j)!j!}k^{j-1}$$

then $$ S= N + \frac{(N+1)!}{(N-1)!2!} k^{1} + \frac{(N+1)!}{(N-2)!3!} k^{2} + \frac{(N+1)!}{(N-3)!4!} k^{3} +... $$

giving $$ S= N + \frac{(N+1)(N)}{2!} k^{1} + \frac{(N+1)(N)(N-1)}{3!} k^{2} + \frac{(N+1)(N)(N-1)(N-2)}{4!} k^{3} +... $$

thus $$ S= N + \frac{N^2+N}{2} k^{1} + \frac{N^3-N}{6} k^{2} + \frac{N^4-2 N^3-N^2+2 N}{24} k^{3} +... $$

For $N=1 to 10,000$ and $k= 2.40242 * 10^{-12}$ this formula can be truncated to $$ S = N + \frac{N^2+N}{2} k^{1} $$ and then gives results very close to those expected. Because $k$ is so small relative to $n$ the terms in higher powers of $k$ can be ignored. Note that the coefficient of $k^1$ is consistent with that found by examination of the coefficients in the "pyramid" presented above.

$\endgroup$
4
  • $\begingroup$ Your parentheses are mismatched on the first formula. Was the intention $\frac{(k+1)(k+1)^N-1}{k}$, or something different? $\endgroup$ Nov 19, 2014 at 13:45
  • $\begingroup$ @Dan. Thanks, sorry, I meant something different. I have corrected the question. $\endgroup$
    – steveOw
    Nov 19, 2014 at 13:51
  • $\begingroup$ $\binom{N+1}{j} = \dfrac{(N+1)!}{(N+1-j)!j!}$, not $\dfrac{(N+1)!}{(N-j)!j!}$. $\endgroup$
    – TonyK
    Nov 19, 2014 at 21:37
  • $\begingroup$ @TonyK Aha! Bingo!. Many thanks for pointing it out:-) $\endgroup$
    – steveOw
    Nov 19, 2014 at 21:46

4 Answers 4

3
$\begingroup$

for $k<1$ we can use $$ (1+k)^N \approx 1+ kN + \frac{N(N-1)}{2}k^2 + \frac{N(N-1)(N-2)}{3!}k^3 $$ thus

$$ \begin{align} \sum (1+k)^i &\approx&\frac{(k+1)(1+ kN + \frac{N(N-1)}{2}k^2 + \frac{N(N-1)(N-2)}{3!}k^3-1)}{k}\\ &=&(k+1)\left(1+\frac{N-1}{2}k+\frac{(N-1)(N-2)}{3!}k^2\right) \end{align} $$

$\endgroup$
7
  • 1
    $\begingroup$ This is especially useful for ridiculously tiny $k$; the smaller $k$ is, the better the approximation. $\endgroup$ Nov 19, 2014 at 13:59
  • $\begingroup$ I know right. Hopefully, this was what the OP intended to get an answer about. Thanks! $\endgroup$
    – Chinny84
    Nov 19, 2014 at 14:09
  • $\begingroup$ @Chinny84. Thanks. But in the range which I am interested $N$ ranges from 1 to 10,000 and I expect to see a non-linearity in S due to effect of $k^2$. $\endgroup$
    – steveOw
    Nov 19, 2014 at 16:03
  • $\begingroup$ Expand terms in my first expression to include higher order terms in $k$? Does that help you ? $\endgroup$
    – Chinny84
    Nov 19, 2014 at 16:10
  • $\begingroup$ Although I'm familiar with the approximation in your first expression I'm not sure what you mean by expanding it to higher orders of k and applying that result thereafter. $\endgroup$
    – steveOw
    Nov 19, 2014 at 17:20
2
$\begingroup$

Using $$ \sum_1^N (1+k)^i = \frac{(k+1)\,((k+1)^N-1)}{k}$$

(which since this is a geometric series is not hard to prove) we get

$$ \sum_1^N (1+k)^i = \frac{\left(\sum_{j=0}^{N+1}\binom{N+1}{j}k^j\right) - (k+1)}{k}$$

$$ = \frac{1 + (N+1)k + \left(\sum_{j=2}^{N+1}\binom{N+1}{j}k^j\right) - (k+1)}{k}$$

$$ = N + \sum_{j=2}^{N+1}\binom{N+1}{j}k^{j-1}$$

$\endgroup$
6
  • $\begingroup$ ah yes, thankyou! $\endgroup$ Nov 19, 2014 at 14:57
  • $\begingroup$ Thanks. It looks promising. I am following on in an update section at the end of my question. $\endgroup$
    – steveOw
    Nov 19, 2014 at 17:23
  • $\begingroup$ Please see the Update at end of the question. My expansion of your formula misses the mark but a similar formula gets very close to the expected values. $\endgroup$
    – steveOw
    Nov 19, 2014 at 21:31
  • $\begingroup$ @steveOw: You made a mistake $-$ see my comment to your question. $\endgroup$
    – TonyK
    Nov 19, 2014 at 21:39
  • $\begingroup$ @TonyK. You are right, many thanks. $\endgroup$
    – steveOw
    Nov 19, 2014 at 21:49
2
$\begingroup$

There is nowhere a converging series in sight. From the data given it seems that $N$ is large and $$p:=Nk$$ is very small. Therefore we may write $$S={1+k\over k}\bigl((1+k)^N-1\bigr)={1+k\over k}\left(\bigl(1+{p\over N}\bigr)^N-1\right)\doteq{1+k\over k}(e^p-1)\ .$$ If $N$ is not in the thousands use the first few terms of the binomial series: $$\left(1+k\right)^N-1=\sum_{j=1}^\infty{N\choose j}k^j\ .$$

$\endgroup$
1
  • $\begingroup$ @Christian.Thanks. The logic looks good. But in Excel, although the values of S look approximately right as N increases from 1 to 10,000 there is a ripple of approximately +/-0.2 *10^{-5} superimposed. I think this is due to a problem with truncation in excel but Ihavent narrowed it down to a particular term yet. $\endgroup$
    – steveOw
    Nov 19, 2014 at 15:58
0
$\begingroup$

An alternative approach using binomial coefficients:

$$\begin{align} \sum_{i=1}^{N}(1+k)^i&=\sum_{i=1}^N\sum_{r=0}^i \binom ir k^r\\ &=k^0\sum_{i=1}^N\binom i0+\sum_{r=1}^Nk^r\sum_{i=r}^N\binom ir\\ &=N+\sum_{r=1}^Nk^r\binom{N+1}{r+1} \end{align}$$


NB - the result is the same as $$\qquad N+\sum_{r=2}^{N+1}k^{r-1}\binom {N+1}r$$

$\endgroup$

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.