Cтраница 3
Пусть заданы одноместная функция / 5 и фиксированное натуральное число с. Ее общее определение может быть сформулировано с помощью следующих двух соотношений: ф ( 0) с - базис индукции; ф ( х 1) J5 ( Ф ( х)) - индукционный шаг. [31]
Существуют только четыре функции от одного аргумента. Четвертая, ( 00), имеет тривиальную сложность. Таким образом базис индукции выполняется. [32]
В этом случае индукционный шаг делать можно, но непосредственно проверяется, что при п3 неравенство 2 п2 неверно, так что начинать индукцию нельзя. Лишь при п5 это неравенство справедливо, так что за базис индукции можно взять Ио5; при п 5 индукционный шаг также проходит. [33]
В этом случае индукционный шаг делать можно, но непосредственно проверяется, что при п3 неравенство 2 п2 неверно, так что начинать индукцию нельзя. Лишь при п 5 это неравенство справедливо, так что за базис индукции можно взять о5; при п: г 5 индукционный шаг также проходит. [34]
Покажем индукцией по т, где т - степень числа 2, что если А имеет ранг т, то МНОЖИТЕЛЬ вычислит такие L, U и Р, что A - LUP и L, U, Р - нижняя треугольная матрица, верхняя треугольная матрица и матрица перестановки рангов т, т, п соответственно. Если / п1, то в Л должен быть ненулевой элемент, так что базис индукции выполняется. Поэтому матрица Е-1, необходимая в строке 9, существует. [35]