Sum of n with factoral exponent

Question

I'm not sure what this is called, but the application is in counting the number of nodes in a consistently branching structure.

For example, $5$ nodes branch into $5$ nodes each, each branching again, etc, $5$ times overall.

I think the math would be:

$5^1 + 5^2 + 5^3 + 5^4 + 5^5 = 3905$

I'm just looking for a better way of calculating this. I looked up exponent rules, and they did not cover this scenario.

Answer 1

This is known as a geometric series. Look up Geometric Series. Specifically if you want to find the sum of $a+ar+ar^2+\cdots+ar^{n-1}$, the formula is as follows: $$\sum_{k=0}^{n-1}ar^k=a\left(\dfrac{1-r^n}{1-r}\right)$$ where $r$ is the common ratio of the Geometric Progression.

---

For the specification you have mentioned, you just have to put in $\begin{bmatrix}a \\ r\end{bmatrix}=\begin{bmatrix}5 \\ 5\end{bmatrix}$.

Answer 2

Let $q\in \mathbb{R}$, $q\neq 1$, and $n\in \mathbb{N}$. It holds that $$ q+q^2+\ldots + q^n = \frac{q}{1-q}(1-q^n). $$

Proof. Let $S_n=q+q^2+\ldots + q^n$. Then $$ qS_n=q^2+\ldots+q^{n+1} $$ and $$ S_n-qS_n=q-q^{n+1}=q(1-q^n), $$ from which it is easy to conclude. $\Box$