Finding the sum of $3+4\cdot 3+4^2\cdot 3+\dots +4^{\log n-1} \cdot 3$

Question

I see this:

$$A=3+4\cdot 3+4^2\cdot 3+\dots +4^{\log n-1} \cdot 3=3\cdot ([4^{\log n}-1]/3)=n^2-1$$

The base of logarithm is $2$, and $n$ is $2,4,8,\dots$

Anyone could describe me how this sum was calculated? Some hints or some tutorial for this?

Answer 1

If $\log $ is 2-base logarithm, you have: $\;\;\; 3+4 \cdot 3+4^2 \cdot 3+ \cdots + 4^{\log n -1} \cdot 3 \\ = 4-1+4(4-1)+4^2(4-1)+4^3(4-1)+\cdots+4^{\log n -1} \cdot (4-1) \\ = 4-1+4^2-4+4^3-4^2+\cdots+4^{\log n}-4^{\log n-1} \\ = 4^{\log n}-1 \\ = 2^{2\log n}-1 \\ = n^2-1$

$\textbf{Edit}$ In sigma notation :

$$\sum_{i=1}^{\log n}3\cdot 4^{i-1}=\sum_{i=1}^{\log n}(4-1)\cdot 4^{i-1}=\sum_{i=1}^{\log n}4^{i}-4^{i-1}=\sum_{i=1}^{\log n}4^{i}-\sum_{i=1}^{\log n}4^{i-1}=4^{\log n}-1$$

Answer 2

$$\begin{align}S&=3+3\cdot 4+3\cdot 4^2+3\cdot 4^3+...+3\cdot 4^{\log_2 n-1}\\ &=3[1+4+4^2+4^3+...+4^{\log_2 n-1}]\\ 4S&=3[\quad\;\; 4+4^2+4^3+...+4^{\log_2n-1}+4^{\log_2 n}] \quad \quad \text{as $n=1,2,4,8,...,2^m,...$} \end{align}$$ Subtracting: $$\begin{align} 3S&=3[4^{\log_2n}-1]\\ &=3[2^{2\log_2n}-1]\\ &=3[(2^{\log_2 n})^2-1]\\ &=3[n^2-1]\\ S&=n^2-1\end{align}$$

Note: The use of $n$ here is unconventional in that it is not the index count, i.e. $n\neq 1, 2, 3, 4, ....$ but instead $n=2^m=1, 2, 4, 8, 16, ...$

Answer 3

Maybe we need to take a few steps back ( though I imagine this has all been covered in your course). If $a$ is any real number other than $1$ and $r$ is a positive integer, then $1 + a + a^{2} +\ldots +a^{r-1} = \frac{a^{r}-1}{a-1}.$ If you need to verify that, multiply the left side by $a-1$ and notice that there is a lot of cancellation. If $b$ is another real number, then we see that $b + b.(a) + b.(a^{2}) +\ldots +b.(a^{r-1}) = b.\frac{a^{r}-1}{a-1}.$

In this problem, $b =3, a= 4$ and $r = \log_{2}(n)$ (where, although it not explcitly said, $n$ must be a (positive integer) power of $2)$. Then $a^{r} = 2^{2\log_{2}(n)} = n^{2}.$ Also, $b = 3,$ and $a-1 = 3,$ so the answer does indeed simplify to $n^{2}-1.$