1. Limited time only! Sign up for a free 30min personal 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!

I Proving that a solution to a recurrence relation is true

  1. Nov 5, 2016 #1
    I am a little confused about how we prove that a solution for a recurrence relation is correct. For example, say that I have the recurrence relation ##H_n = 2H_{n-1} +1##. Using an iterative process, we guess that the solution is ##2^n - 1##. Now, to prove that this is correct, it seems that it would be sufficient to just plug it into the original recurrence relation to see if everything checks out. However I have seen some sources that claim we also need to use induction on ##H_n = 2^n - 1## to verify that it is true. Why do I have to do both to prove that it is true? Why can't I just do the former or just do the latter?
     
  2. jcsd
  3. Nov 5, 2016 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Plugging it in is equivalent to the induction step.
    If you have no starting value given, there is no need for the start of the induction, so both approaches are identical.

    Hn = 2n-1 is not the only solution by the way.
     
  4. Nov 5, 2016 #3
    What if I do have a starting value, ##H_1 = 1##? Would proof by induction be the only valid way in this case?
     
  5. Nov 5, 2016 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You would have to show that your solution also satisfies this starting value. And then your approach is identical to full induction.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proving that a solution to a recurrence relation is true
  1. Recurrence relation (Replies: 6)

  2. A recurrence relation (Replies: 7)

Loading...