I am reading Algorithm's Design Manual by S.Skiena and I have a hard time understanding and proving the correctness of algorithms. I should use proof by induction and when we talk about summations and proving their formulas I can do it, I have no problem understanding why it is correct. When I get a loop on the other hand, I cannot even get started. I have a hard time combining the Loop invariant (also finding it) and the proof.
For example the following is a complete mystery (i tried reading a few similar questions on SO, but I still don't get it)
function multiply(y, z) if z = 0 then return(0) else return(multiply(cy, ⌊z/c⌋) + y · (z mod c))
I understand that I am asking a lot, but is it possible for someone to try to explain it step by step ? I am learning the book on my own, this is not a homework and I am not trying to cheat on anything, I just do not understand it.