Proving that a solution to a recurrence relation is true

[Mr Davis 97]

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?

 

[mfb]

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.

H_n = 2ⁿ-1 is not the only solution by the way.

 

[Mr Davis 97]

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.

H_n = 2ⁿ-1 is not the only solution by the way.

What if I do have a starting value, $H_1 = 1$? Would proof by induction be the only valid way in this case?

 

[mfb]

You would have to show that your solution also satisfies this starting value. And then your approach is identical to full induction.