Originally Posted by

**taurus** I need to prove: SUM[3^k]for k=0..n <= c3^k.

Now the steps I have done is as follow:

Base case is 1:

SUM[3^k]for k=0..n = 1 <= c.1 as long as c>1

This is no base case at all: it must be $\displaystyle 3^0+3^1=4$ (for n=1) and then you must prove this is less than or equal $\displaystyle c\cdot 3^1$, for some constant c...

What you did is the inductive assumption or hypothesis.

Now the induction case:

SUM[3^k]for k=0..n+1 = SUM[3^k]for k=0..n + 3^(n+1)

<= c3^n + 3^(n+1)

Now from there I do not know how to go on

Could someone help.

Thanks