Нужна помощь в понимании объяснения индукционного доказательства для алгоритма

---

Мне трудно понять, как автор Стивен Скиена из книги The Algorithm Design Manual использовал метод индукции для доказательства следующего алгоритма, который представляет/возвращает y = y + 1 в псевдокоде:

Increment(y)
        if y = 0 then return(1) else
            if (y mod 2) = 1 then
                 return(2 · Increment(y/2)) 
            else return(y + 1)

В частности, я не понимаю, как он получил от первого уравнения/равенства 2·инкремент(м + 1/2) к следующему 2·инкремент(м) в приведенном ниже доказательстве. В своем полном тексте он утверждает, что:

"Для нечетных чисел ответ зависит от того, что возвращается приращением(y/2). Здесь мы хотим использовать наше индуктивное предположение, но оно не совсем верно. Мы предположили, что инкремент работает правильно для y = n − 1, но не для значения, которое составляет примерно половину его. Мы можем решить эту проблему, укрепив наше предположение и объявив, что общий случай справедлив для всех y ≤ n−1. Это нам в принципе ничего не стоит, но необходимо для установления правильности алгоритма.

Теперь можно рассмотреть случай нечетного y (т. е. y = 2m + 1 для некоторого целого числа m)
как:

2·Increment((2m + 1)/2) = 2·Increment(m + 1/2)
                        = 2·Increment(m)
                        = 2(m + 1)
                        = 2m +2 = y + 1

"

Что я уже пробовал:

Я понимаю, что алгоритм рекурсивен и что он корректен как для четных, так и для нечетных чисел, всегда увеличивающих входное значение y. Однако автор использует индукцию для доказательства алгоритма, и для случая, когда y = m + 1, я не знаю, почему + 1/2 просто исчез. Я не думаю, что это подходит для случаев, когда m просто настолько велико, что 1/2 почти несущественно, поскольку мы говорим о том, является ли m + 1 четным или нечетным.

---