# How would you prove $\sum_{i=1}^{n} (3/4^i) < 1$ by induction?

How would you prove this by induction?

$$\sum_{i=1}^{n} \frac{3}{4^i} < 1 \quad \quad \forall n \geq 2$$

I can do the base case but don't know how to to finish it.

-

HINT: The first few sums are $\frac34=1-\frac14$, $\frac34+\frac3{16}=\frac{15}{16}=1-\frac1{16}$, and $\frac{15}{16}+\frac3{64}=\frac{63}{64}=1-\frac1{64}$. This should suggest the conjecture that

$$\sum_{i=1}^n\frac3{4^i}=1-\frac1{4^i}\;;$$

try proving that by induction instead. This is a good illustration of the (perhaps surprising) fact that sometimes it’s easier to prove a stronger statement than a weaker one.

-
Thanks a lot it was a lot easier to proof it with $1 - \frac{1}{4^i}$ –  jack Mar 24 '13 at 22:53
@jack: You’re very welcome. –  Brian M. Scott Mar 24 '13 at 23:01

Hint: if $S_n = \sum_{i=1}^n 3/4^i$, $S_{n+1} = 3/4 + S_n/4$.

-

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

-