Доказать утверждение методом математической индукции

@Alinmora · Регистрация: 11.10.2015

Author24 — интернет-сервис помощи студентам

Здравствуйте! Имеется следующее утверждение, касающееся бинарных деревьев: если номер узла i, то его потомки имеют номера 2i, 2i+1
Нужно доказать это методом математической индукции.

Спасибо за помощь!

echs · 02.06.2016, 17:10

Alinmora
Доказательство с помощью математической индукции
совершается в два этапа.
1. Должно быть верно базовое утверждение, что при i = 1
потомки имеют номера 2 и 3 (у вас этого нет, но допустим
вы про это забыли). Это важно. Иначе никакого доказательства
не получится.
2. Теперь допустим, что при i = k потомки имеют номера 2k и 2k+1
И рассмотрим следующие по порядку номера 2k+2 и 2k+3
Запишем их так 2(k+1) и 2(k+1) +1. То есть это потомки числа
i = k + 1. следующего за i = k.
А значит это верно для всех натуральных чисел.
Что и требовалось доказать.

@Alinmora 1 / 1 / 0 Регистрация: 11.10.2015 Сообщений: 32
		1
	Доказать утверждение методом математической индукции 01.06.2016, 09:21. Показов 579. Ответов 1 Метки нет (Все метки) Здравствуйте! Имеется следующее утверждение, касающееся бинарных деревьев: если номер узла i, то его потомки имеют номера 2i, 2i+1 Нужно доказать это методом математической индукции. Спасибо за помощь! 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	02.06.2016, 17:10	2
	Alinmora Доказательство с помощью математической индукции совершается в два этапа. 1. Должно быть верно базовое утверждение, что при i = 1 потомки имеют номера 2 и 3 (у вас этого нет, но допустим вы про это забыли). Это важно. Иначе никакого доказательства не получится. 2. Теперь допустим, что при i = k потомки имеют номера 2k и 2k+1 И рассмотрим следующие по порядку номера 2k+2 и 2k+3 Запишем их так 2(k+1) и 2(k+1) +1. То есть это потомки числа i = k + 1. следующего за i = k. А значит это верно для всех натуральных чисел. Что и требовалось доказать. 0