Искусство компьютерного программирования (2-е изд.): Математическая индукция

Question

В разделе 1.2.1 "Математическая индукция" Кнут представляет математическую индукцию как двухэтапный процесс, чтобы доказать, что P (n) верно для всех натуральных чисел n:

а) Дайте доказательство того, что P (1) верно;

б) Дайте доказательство того, что "если все P(1), P(2),..., P(n) верны, то P(n+1) также верно";

У меня есть серьезные сомнения по этому поводу. Действительно, я считаю, что пункт б) должен быть:

б) Дайте доказательство того, что "если P (n) истинно, то P(n+1) также верно". Основное различие заключается в том, что вы предполагаете, что P (n) истинно, а не P(n-1) и т. Д.

Тем не менее, эти книги старые и были прочитаны многими людьми (большинство из них гораздо умнее, чем я ^^).

Так в чем же здесь мое замешательство?

Answer 1

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