Recurence Relation, specifically understanding substitution rule used

Question

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?

Answer 1

$$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.$$

Answer 2

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.