1

Is there an O(1) (uses a function instead of summation/for loop notation) way to calculate $$ \sum\limits_{i=0}^n x^i $$ Given (x,n) Example: (4,3) 64+16+4+1 (3,3) 27+9+3+1 (2,10) 1024+...+8+4+2+1 I know that for x=2, f(x,n)=(x^(n+1))-1 I am in search of a general solution for all x,n.

Starfy_S
  • 21
  • $$f(x,n) = \frac{x^{n+1}-1}{x-1},$$ unless $x = 1$, in which case $f(1,n) = n+1$. – Daniel Fischer Mar 13 '14 at 21:10
  • http://en.wikipedia.org/wiki/Geometric_series#Formula – rlartiga Mar 13 '14 at 21:11
  • Thanks, it just dawned upon me that this was a geometric series. I had been searching for terms that seemed to fit this, but terminology kills me. I came across this in the process, which has other relevant information. http://mathworld.wolfram.com/GeometricSeries.html – Starfy_S Mar 13 '14 at 21:14

1 Answers1

3

This is a geometric progression. The general formula is given by $$f(x,n) = \sum_{i=0}^n x^i = \begin{cases}\frac{x^{n+1}-1}{x-1} & x\neq 1\\ n+1 & x=1\end{cases}$$ Assuming $0^0 = 1$

AlexR
  • 24,905