1
$\begingroup$

Wolfram Alpha provides the following exact solution $$ \sum_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_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$ – Dan Uznanski Nov 19 '14 at 13:45
  • $\begingroup$ @Dan. Thanks, sorry, I meant something different. I have corrected the question. $\endgroup$ – steveOw Nov 19 '14 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 '14 at 21:37
  • $\begingroup$ @TonyK Aha! Bingo!. Many thanks for pointing it out:-) $\endgroup$ – steveOw Nov 19 '14 at 21:46
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$ – Christopher Nov 19 '14 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 '14 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 '14 at 21:31
  • $\begingroup$ @steveOw: You made a mistake $-$ see my comment to your question. $\endgroup$ – TonyK Nov 19 '14 at 21:39
  • $\begingroup$ @TonyK. You are right, many thanks. $\endgroup$ – steveOw Nov 19 '14 at 21:49
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$ – Dan Uznanski Nov 19 '14 at 13:59
  • $\begingroup$ I know right. Hopefully, this was what the OP intended to get an answer about. Thanks! $\endgroup$ – Chinny84 Nov 19 '14 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 '14 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 '14 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 '14 at 17:20
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 '14 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.