I'm having trouble understanding how the author Steven Skiena of the book The Algorithm Design Manual used the induction method to prove the following algorithm that represents/returns y = y + 1 in pseudocode:
Increment(y)
if y = 0 then return(1) else
if (y mod 2) = 1 then
return(2 · Increment(y/2))
else return(y + 1)
Specifically I don't understand how he got from the first equation/equality
2·Increment(m + 1/2) to the next one
2·Increment(m) in the proof below. In his full text he states that:
"For the odd numbers, the answer depends upon what is returned by Increment(y/2). Here we want to use our inductive assumption, but it isn’t quite right. We have assumed that increment worked correctly for y = n − 1, but not for a value which is about half of it. We can fix this problem by strengthening our assumption to declare that the general case holds for all y ≤ n−1. This costs us nothing in principle, but is necessary to establish the correctness of the algorithm.
Now, the case of odd y (i.e. y = 2m + 1 for some integer m) can be dealt with
as:
2·Increment((2m + 1)/2) = 2·Increment(m + 1/2)
= 2·Increment(m)
= 2(m + 1)
= 2m +2 = y + 1
"
What I have tried:
I understand that the algorithm is recursive and that it is correct for both even and odd numbers always incrementing the input value of y. However, the author is using induction to prove the algorithm and for the case where y = m + 1, I don't know why the + 1/2 just dissapeared. I don't think it fits the cases where m is just to big that 1/2 is almost insignificant since we're talking whether m + 1 is even or odd.