# How do I express the sum $(1+k)+(1+k)^2+(1+k)^3…+(1+k)^N$ for $|k|<<1$ as a series?

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.

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

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

• ah yes, thankyou! – Christopher Nov 19 '14 at 14:57
• Thanks. It looks promising. I am following on in an update section at the end of my question. – steveOw Nov 19 '14 at 17:23
• 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. – steveOw Nov 19 '14 at 21:31
• @steveOw: You made a mistake $-$ see my comment to your question. – TonyK Nov 19 '14 at 21:39
• @TonyK. You are right, many thanks. – steveOw Nov 19 '14 at 21:49

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}

• This is especially useful for ridiculously tiny $k$; the smaller $k$ is, the better the approximation. – Dan Uznanski Nov 19 '14 at 13:59
• I know right. Hopefully, this was what the OP intended to get an answer about. Thanks! – Chinny84 Nov 19 '14 at 14:09
• @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$. – steveOw Nov 19 '14 at 16:03
• Expand terms in my first expression to include higher order terms in $k$? Does that help you ? – Chinny84 Nov 19 '14 at 16:10
• 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. – steveOw Nov 19 '14 at 17:20

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

• @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. – steveOw Nov 19 '14 at 15:58

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