mathematic induction, how to prove that this work in this recursive function

Question

i'm reading this book: The Algorithm Design Manual, and i'm having a problem to understand, it's about inductive assumption, so i've this 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)

So i've to prove through mathematic induction that this code really work, the first part is easy:

if y = 0 
    then return(1)

The last part is easy too, it's get even number

else 
    return(y + 1)

But middle part being very difficult for me:

else if (y mod 2) = 1 
   then return(2 · Increment(⌊y/2⌋))

here is the explanation of the book:

Now, the case of odd y (i.e. y = 2m + 1 for some integer m) can be dealt with as:
(y = 2m + 1; because 2m + 1 is equal to any odd number)//this is what i understand

= 2 · Increment(⌊(2m + 1)/2⌋)//(2m + 1)/2 = m + 1/2
= 2 · Increment(⌊m + 1/2⌋)//ok we get here, but how (m + 1/2) will be the "m" bellow?
= 2 · Increment(m)
= 2(m+1)
= 2m+2 =y+1

Anyone could explain how to prove that this recursive really work? And how prove this by mathematic induction.

Answer 1

= 2 · Increment(⌊m + 1/2⌋) //ok we get here, but how (m + 1/2) will be the "m" bellow?

Because ⌊m + 1/2⌋ = m, that's as simple as that. (I'm assuming you know that ⌊m + 1/2⌋ means floor(m + 1/2).

Note that m is an integer, and given that 1/2 is fractional, then floor(m+1/2) is m. In fact, floor(m + x), where 0 <= x < 1, is just m: adding any fractional part to m does not change the result of floor().

So you get 2 * Increment(m) = 2(m+1) = 2m+2 = (2m+1)+1 = y+1

UPDATE: Proof by induction is pretty similar.

Recall the general layout of proof by induction: first, we elaborate the induction hypothesis. Then, we show that this hypothesis holds for a base case (usually, a base case is when n = 0, or n = 1). Last, but not least, we show, using the hypothesis, that if it works for some value of n, then it also works for n+1. Since the hypothesis works for the base case, and because we showed (with an induction step) that if it works for n, then it works for n+1, then it must be true for every value greater than or equal to the base case value.

Hypothesis

In this specific case, our hypothesis is that this function:

I(n) = 1 if n is 0
       n+1 if n is even
       2 * I(floor(n / 2)) otherwise

is equal to n+1, that is,

I(n) = n+1

Where I(n) is just a short hand notation for Increment(n). You can also see the hypothesis as a set of 3 mathematical statements (in other words, the hypothesis is that each of the three cases evaluates to n+1 in the conditions stated).

Base case

The base case is when n = 0. For n = 0, I(n) evaluates to 1, which is n+1 (with n being 0), so we have proven that the hypothesis works for n = 0.

Now, we want to prove that if our hypothesis works for n, then it works for n+1.

Induction step

If I(n) = n+1 holds, then I(n+1) = (n+1)+1 must be true. Basically, we are saying, "OK, if I(n) evaluates to its argument plus one, then it means that I(n+1) must be (n+1)+1. This is what we have to prove: we must show that I(n+1) = (n+1)+1.

Now, according to the original definition for I(n), we have two cases: either its argument is even, or it is odd.

This time, the argument to the function I is n+1 - let's consider both cases.

If n+1 is even, by the definition of I(n), we can immediately see that I(n+1) = (n+1)+1.

If n+1 is odd, then we know that n+1 = 2m+1 for some integer m, because if n+1 is odd, then n is even, which means that there is an integer m less than n such that 2m = n. So, we can rewrite n+1 as 2m+1:

I(n+1) = I(2m + 1) = 
       = 2 * I(floor((2m+1) / 2)) =
       = 2 * I(floor(m + (1/2)) =
       = 2 * I(floor(m)) = // we can remove 1/2 for the same reason
       = 2 * I(m) =
       = 2 * (m+1) = // inductive step; we used the hypothesis that I(n) = n+1
       = 2*m + 2 = 
       = (2*m+1) + 1 =
       = (n+1) + 1

This shows that if the proposition is true for floor(n/2) (because m is n/2), then it is also true for n+1. By using strong induction, we can prove that if the proposition is true for all m, 0 <= m <=n, it is also true for n+1 (see comment below).

So, indeed, I(n+1) = (n+1)+1 for any integer, assuming that I(n) = n+1 is valid.

We showed that the hypothesis works for n+1 if it works for n, and we showed that it works for n = 0. Thus, it works for n >= 0.