Рассчитать количество узлов из числа дуг в дереве - Индукция

Question

Если дерево имеет k дуг, сколько у него узлов?

Базовый вариант:

If k=0 => n=(k+1)=1

Индуктивная гипотеза: For every k, n=(k+1) is true

Доказательство:

Is it true for k=1?
k=n-1
1=n-1
1=(k+1)-1
k=1,so:
1=1+1-1
1=1
Proved?

Я что-то пропустил?

Answer 1

Вы никогда не хотите использовать 0 или 1 в качестве базового варианта для доказательства по индукции

If k=0 => n=(k+1)=1

Вы можете доказать все, что вы хотите, если вы используете 0 (или часто 1) в качестве базового варианта. Классическим примером этого является то, что все лошади одного цвета. Это твоя ошибка.

Кроме того, вы можете сделать так, чтобы графы с одинаковым количеством дуг имели разное количество узлов, что сразу показывает, что вы не сможете использовать доказательство по индукции для решения вашей проблемы.

Удачи!