0

I started my data structures course at university and I came across with that equation, can someone explain me how I prove it please?

$$\sum_{i=0}^{\log_3{n}}3^i = \frac{3n - 1}{2}$$ $$3^0+3^1+ ...+3^{\log_3 (n)} = \frac{3n-1}{2}$$ $$2(3^0+3^1+ ...+3^{\log_3 (n)}) = 3n-1$$ $$2+2\cdot3+2\cdot3^2 + ...+2\cdot3^{\log_3 (n)} = 3n-1$$ $$3+2\cdot3+2\cdot3^2 + ...+2\cdot3^{\log_3 (n)} = 3n$$ $$\frac{3+2\cdot3+2\cdot3^2 + ...+2\cdot3^{\log_3 (n)}}{3} = n$$ $$\frac{3(1+2+2\cdot3 + ...+2\cdot3^{\log_3 (n) -1})}{3} = n$$ $$1+2+2\cdot3 + ...+2\cdot3^{\log_3 (n) -1} = n$$ $$3+2\cdot3 + ...+2\cdot3^{\log_3 (n) -1} = n$$

Can I continue from here?

LiziPizi
  • 2,855

1 Answers1

1

Use the formula for sum of geometric (finite) series:

$$\sum_{i=0}^{\log_3n}3^i=\frac{3^{\log_3n+1}-1}{3-1}=\frac{3n-1}2$$

In general:

$$\sum_{k=0}^M r^k=\frac{r^{M+1}-1}{r-1}$$

You can prove this formula by induction.

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
  • You want $M$ in your general formula, not $k$. Also, there is a simpler algebraic proof: $rS_M=S_M-1+r^{k+1}$, solve for $S_M$. – Ian Mar 19 '16 at 16:04
  • @Ian Thank you, Of course itmust be $;M;$ . Typo corrected. That algebraic formula also uses hidden induction, I believe. – DonAntonio Mar 19 '16 at 16:11
  • Rigorously yes, you have to use induction to get $rS_M=S_M-1+r^{M+1}$, but that's just because it is a statement about all natural numbers. It is clear what is going on without having to explicitly write out the induction. – Ian Mar 19 '16 at 16:13
  • @Ian Thank you. True, I agree with you. Yet someone very strict could require induction. – DonAntonio Mar 19 '16 at 16:16