Summation of differences in exponent

57 Views Asked by At

Came to this summation during an algorithm analysis problem and any help would be much appreciated:$$\sum_{j=1}^n3^{n-j}$$

2

There are 2 best solutions below

5
On BEST ANSWER

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

func(n)
{
    return n==0 ? 0 : (pow(3,n)+func(n-1));
}
0
On

Hint: $$\sum_{j=1}^n3^{n-j}=3^n\sum_{j=1}^n\frac{1}{3^j}$$