1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solve the recurrence relation using iteration

  1. Dec 5, 2014 #1
    1. The problem statement, all variables and given/known data

    Solve the recurrence relation (use iteration).

    an = an-1 + 1 + 2n-1
    a0 = 0

    Then prove the solution by mathematical induction.

    2. Relevant equations


    3. The attempt at a solution

    a1 = 2
    a2 = 5
    a3 = 10
    a4 = 19
    a5 = 36

    The solution appears to be an = n + 2n - 1

    How are we supposed to get that though? I just guessed and did trial and error. That's really the only/primary way?

    Also, what are the properties of this recurrence relation (e.g., linear, homogeneous, etc.)? Why?

    Also sorry if this is posted in the wrong section, I didn't know where it belongs if not here.

    So how do I prove (or disprove, since I've only tried it out for so many of these) my solution using induction?

    Thank you so much.
     
    Last edited: Dec 5, 2014
  2. jcsd
  3. Dec 5, 2014 #2

    pasmith

    User Avatar
    Homework Helper

    [itex]a_1 = a_0 + 1 + 2^0 = 1 + (2 - 1)[/itex]
    [itex]a_2 = a_1 + 1 + 2^1 = 1 + 2^0 + 1 + 2^1 = 2 + (1 + 2) = 2 + (4 - 1)[/itex]
    [itex]a_3 = a_2 + 1 + 2^2 = 2 + (1 + 2) + 1 + 2^2 = 3 + (1 + 2 + 4) = 3 + (8 - 1)[/itex]
    etc...

    Can you spot any patterns?
     
  4. Dec 5, 2014 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Use the fact that ##a_n - a_1 = (a_n - a_{n-1}) + (a_{n-1} - a_{n-2}) + \cdots + (a_2 - a_1)##, and you have a formula for ##a_k - a_{k-1}##.
     
  5. Dec 6, 2014 #4
    Yeah that's what I did.

    So how do I prove my solution by induction?
     
  6. Dec 6, 2014 #5
    What's that formula for though?

    For proof by induction I need to make ##a_{k+1} = (k+1) + 2^{k+1} -1## right?
     
  7. Dec 6, 2014 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Are you claiming that you have never seen the formula for ##\sum_{k=1}^n r^k##? You can look in books or on-line for an answer.

    HInt: geometric series.
     
    Last edited: Dec 6, 2014
  8. Dec 6, 2014 #7

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    What does linear mean? What does homogeneous mean? These are basic definitions you should look up for yourself.

    There's a bit more to it. There are two parts to a proof by induction. Do you know what they are? If not, you should find out what they are. Apparently, this is something you're already supposed to know.
     
  9. Dec 6, 2014 #8
    Yeah. I know. You do the base step, then the induction step. I didn't have the starting form right, was confused about what I was supposed to actually be proving... I was just thinking to prove the k+1 part but what I'm supposed to be proving is that the initial recurrence relation formula given is equal to the one I got. Once I realized that (I know, seems painfully obvious), I got it. Thanks.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted