Came to this summation during an algorithm analysis problem and any help would be much appreciated:$$\sum_{j=1}^n3^{n-j}$$
2025-01-13 07:56:06.1736754966
Summation of differences in exponent
57 Views Asked by Jakub Kawalec https://math.techqa.club/user/jakub-kawalec/detail At
2
This is a geometric series. $$\sum_{j=1}^n3^{n-j}=3^{n-1}+3^{n-2}+...$$ The first term is $3^{n-1}$, the common ratio is $\frac{1}{3}$, and there are $n$ terms. Thus, $$\sum_{j=1}^n3^{n-j}=3^{n-1} \cdot \frac{1-(\frac{1}{3})^{n}}{1-\frac{1}{3}}$$ If a recursive algorithm is necessary, try