Facebook Page
Twitter
RSS
+ Reply to Thread
Results 1 to 3 of 3
  1. Pessimist Singularitarian
    MHB Coder
    MHB Math Helper
    MHB Ambassador
    MarkFL's Avatar
    Status
    Offline
    Join Date
    Feb 2012
    Location
    St. Augustine, FL.
    Posts
    10,851
    Thanks
    31,052 times
    Thanked
    25,911 times
    Thank/Post
    2.388
    Trophies
    20 Highscores
    Awards
    MHB Statistics Award (2016)  

MHB Calculus Award (2016)  

MHB Pre-University Math Award (2016)  

MHB Model Helper Award (2015)  

MHB Calculus Award (2015)
    #1
    I was recently sent the following question via PM (which we discourage here), so I thought I would start a thread and help here (and give the OP a link to this thread). Here's the question:



    (a) We can observe that we may write:

    $ \displaystyle 2\cdot\sum_{k=0}^{n}\left(3^k\right)=2\cdot\sum_{k=0}^{n-1}\left(3^k\right)+2\cdot3^n$

    Hence:

    $ \displaystyle S(n)=S(n-1)+2\cdot3^n$

    Now, if we were to derive a closed form for $S(n)$ from the above linear inhomogeneous recursion, we would observe that the homogeneous solution is:

    $ \displaystyle h_n=c_1$

    And, we would be looking for a particular solution of the form:

    $ \displaystyle p_n=A3^n$

    So, to use the method of undetermined coefficients, we would substitute $p_n$ into the recursion to get:

    $ \displaystyle A3^n-A3^{n-1}=2\cdot3^n$

    Divide through by $3^{n-1}$:

    $ \displaystyle 3A-A=6\implies A=3$

    Thus:

    $ \displaystyle p_n=3^{n+1}$

    Hence, by the principle of superposition, we find the general solution to be:

    $ \displaystyle S(n)=h_n+p_n=3^{n+1}+c_1$

    Now, to determine the parameter $c_1$, we find:

    $ \displaystyle S(1)=2(1+3)=8=3^{1+1}+c_1=9+c_1\implies c_1=-1$

    And so we have:

    $ \displaystyle S(n)=3^{n+1}-1$

    This agrees with the induction hypothesis we are to prove for part (b).

    (b) State the induction hypothesis $ \displaystyle P_n$:

    $ \displaystyle 2\cdot\sum_{k=0}^{n}\left(3^k\right)=3^{n+1}-1$

    Show the base case $P_1$ is true:

    $ \displaystyle 2\cdot\sum_{k=0}^{1}\left(3^k\right)=3^{1+1}-1$

    $ \displaystyle 2(3^0+3^1)=3^{1+1}-1$

    $ \displaystyle 8=8\quad\checkmark$

    The base case is true, so as our induction step, we may add $2\cdot3^{n+1}$ to each side of $P_n$:

    $ \displaystyle 2\cdot\sum_{k=0}^{n}\left(3^k\right)+2\cdot3^{n+1}=3^{n+1}-1+2\cdot3^{n+1}$

    One the left, incorporate the added term within the sum while on the right combine like terms:

    $ \displaystyle 2\cdot\sum_{k=0}^{n+1}\left(3^k\right)=3\cdot3^{n+1}-1$

    $ \displaystyle 2\cdot\sum_{k=0}^{n+1}\left(3^k\right)=3^{(n+1)+1}-1$

    We have derived $P_{n+1}$ from $P_n$, thereby completing the proof by induction.

  2. MHB Journeyman
    MHB Math Helper

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    521
    Thanks
    214 times
    Thanked
    614 times
    Thank/Post
    1.179
    #2
    Did the person who sent it to you say why? There does not appear to be any question asked.

  3. Pessimist Singularitarian
    MHB Coder
    MHB Math Helper
    MHB Ambassador
    MarkFL's Avatar
    Status
    Offline
    Join Date
    Feb 2012
    Location
    St. Augustine, FL.
    Posts
    10,851
    Thanks
    31,052 times
    Thanked
    25,911 times
    Thank/Post
    2.388
    Trophies
    20 Highscores
    Awards
    MHB Statistics Award (2016)  

MHB Calculus Award (2016)  

MHB Pre-University Math Award (2016)  

MHB Model Helper Award (2015)  

MHB Calculus Award (2015)
    #3 Thread Author
    Quote Originally Posted by HallsofIvy View Post
    Did the person who sent it to you say why? There does not appear to be any question asked.
    The question is in an image hot-linked to a free image hosting site...and I know from experience that they don't always show up, so I will type it out:


    2.) Let $S$ be the function defined over $\mathbb{N}$ by:

    $$S(n)=2\times\sum_{k=0}^n3^k$$
    (a) Give the recursive definition of $S$.

    (b) Prove the following statement by induction:

    for all $n\in\mathbb{N}$, $S(*n)=3^{n+1}-1$

Similar Threads

  1. Recursion and strings
    By delc1 in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 4
    Last Post: May 20th, 2016, 18:20
  2. Recursion problem in C++
    By FallArk in forum Computer Science
    Replies: 12
    Last Post: April 22nd, 2016, 17:04
  3. [SOLVED] Help with this recursion function in C++
    By FallArk in forum Computer Science
    Replies: 8
    Last Post: April 17th, 2016, 06:29
  4. Recursion C++
    By ineedhelpnow in forum Computer Science
    Replies: 1
    Last Post: December 14th, 2014, 00:25
  5. Recursion and Strong Induction
    By andrew in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 6
    Last Post: May 4th, 2014, 05:16

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards