Incrementing a natural number is simple as adding $1$ to it, so why would we ever want to think about a fancy way of doing it? All we need to do is to go from $y$ to $y + 1$ , and well, that's pretty obvious.

But, let's take a look at one example:

```
from math import floor
def increment(y):
if y == 0:
return 1
elif y % 2 == 1:
return 2 * increment(floor(y / 2))
return y + 1
```

It's a beautiful recursive algorithm for incrementing natural numbers, taken from Steven Skiena’s *The Algorithm Design Manual*.

But how do we know that it's correct?

The book answers it, by using induction.

The *base case* is when
$y$
equals
$0$
, and if that's the case, we return
$1$
. That is correct:
$0 + 1 = 1$
.

Our *induction hypothesis* is that
$\text{Increment}(n - 1)$
is
$n$
.

We assume that is the case, and go on to show that
$\text{Increment}(n)$
holds as well, that is,
$\text{Increment}(n) = n + 1$
.

When $y$ is an even number (when $y \text{ mod } 2 = 0$ ), we return $y + 1$ in the last line, so that's correct.

So what's the deal with odd numbers, then?

When
$y$
is odd (when
$y \text{ mod } 2 = 1$
), what is returned from the `increment`

function is:

```
2 * increment(floor(y / 2))
```

Remember that we need to prove
$\text{Increment}(n) = n + 1$
, so we need to prove that what we return here is indeed `y + 1`

.

When
$y$
is odd, we can write it as
$2m + 1$
, for some integer
$m$
. In that case, what we have is:

```
2 * increment(floor(((2 * m) + 1) / 2))
```

Or:

Note |
---|

$\lfloor$ and $\rfloor$ indicate the floor function. |

We can simplify it by dividing the terms inside $\text{Increment}$ by $2$ :

Taking the floor of $m + 1/2$ , we have just $m$ (remember that $m$ is an integer):

...which is (by our *induction hypothesis*):

...which is:

We said that $y$ is $2m + 1$ . And the result of our increment function returns $2m + 2$ , which is the correct answer: $y + 1$ 🎉

This is certainly a bit tricky at first, but it provides an important lesson that induction is a solid way of proving correctness, even though most of it feels like magic.

*The lectures based on the book The Algorithm Design Manual can be found here*.

## Top comments (0)