Results 1 to 2 of 2

Math Help - Induction to prove bounding summation

  1. #1
    Member
    Joined
    Sep 2007
    Posts
    222

    Question 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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by taurus View Post
    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 3^0+3^1=4 (for n=1) and then you must prove this is less than or equal 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 \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:

    \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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. summation Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 23rd 2011, 02:21 AM
  2. summation Induction
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: December 23rd 2011, 01:55 AM
  3. summation and mathematical induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 15th 2010, 08:32 AM
  4. Summation Induction help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 18th 2010, 05:20 PM
  5. Induction - Summation
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 24th 2009, 04:12 AM

Search Tags


/mathhelpforum @mathhelpforum