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…

Accepted Answer

= 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`.

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

Solution

Problem