# Thread: Induction to prove bounding summation

1. ## Induction to prove bounding summation

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

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

2. 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

You must show that $\displaystyle \sum^n_{k=0}3^k\leq c\cdot 3^{n+1}$ , but the above is only the sum of a finite geometric sequence so:

$\displaystyle \sum^n_{k=0}3^k=\frac{3^{n+1}-1}{3-1}$ ...well, now check what must the constant c be to ensure the inequality...and do correctly the base case (either for k=0 or for k=1: both are acceptable in induction proofs).

Tonio