# Recurence Relation, specifically understanding substitution rule used

This is a pretty vague question and can be applied to many math problems not just recurrence relations.

Above I fully understand, setting up the recurrence relation from the algorithm given. And how the next step would be plugging and chugging to find a pattern that we can use.

So as shown above, we do not know what M(n-1) is but we do know what M(n) is equal to. So every guide just makes M(n) -> M(n-1) by substracting 1 in the original M(n) and then substracting 1 in M(n-1) as well, making the new equation M(n-1) = M((n-1)-1)+1 so now we "know" what M(n-1) is now and can substitute it in the original equation M(n) = M(n-1)+1 ---> M(n) = [M((n-1)-1)+1]+1 . And this is where I have my question, to me this seems like math magic just subtracting 1 inside the M(n) parenthesis only, what substitution rule is being used here? Am I just horribly overthinking it?

• Did I just severly overthink this?! Would it be like saying 9 = (4) + 5 so 9-1 = (4-1)+5. I think I just answered my own question. I think doing it inside of the M(n) and not something like M(n)-1 messed with me. Sep 9, 2022 at 21:53

$$M(n)=M(n-1)+1$$

can be written

$$M(k)=M(k-1)+1$$

or with any other expression as the argument. E.g.

$$M(n-1)=M(n-1-1)+1.$$

By combining,

$$M(n)=M(n-1)+1=M(n-1-1)+1+1.$$

Repeating,

$$M(n)=M(n-1-1-\cdots1)+1+1+\cdots1.$$

In the end,

$$M(n)=M(0)+n.$$

• This actually helped a ton! Thank you a lot! But just to clarify, you are saying that if you were to change the argument in M(n) -> M(n-1) then you would also have to change the argument in M(n-1) -> M(n-1-1) to keep it equivalent? Like how if you had y = x+1 but you wanted y+1 = ? youd have to had 1 to both sides so it would change to y+1 = x+1+1 to stay equivalent. OR is there NO real said "rule" being used and its more of just an obvious "because you do this, this then has to happen". Sep 11, 2022 at 19:57

I don't know exactly what the question is. Plugging in is mainly used to see the pattern, in your case you might have noted that $$M(1)=1$$, $$M(2)=2$$, and so on.

If you want to prove that $$M(n)=n$$, it's easiest to proceed with induction. The base case is already stated in your first figure and the inductive step isn't very hard either.

But the most difficult thing is often to find a non-recurrent version of $$M$$ to prove the equivalence to, and her unrolling helps.

• Sorry, its hard for me to word the question well! Basically what I'm trying to get at is: lets say you have y = x+1 but you want to know what y+1 =? so you do y+1 = x+1+1 because you have to do on one side that you do to the other, so that the equation stays equivalent. It gets tricker with M(n) = M(n-1)+1, is there some sort of metaphor for explaining why when you want to find M(n-1) you just subtract 1 on the inside like-> M(n-1) = M(n-1-1)+1 instead of like M(n-1) = M(n)-1 by subtracting the one to the otherside. If this is un-understandable please let me know! Sep 10, 2022 at 21:24
• And I realize that M(n-1) != to M(n)-1, so why do we do it one way and not the other. Sep 10, 2022 at 21:30