Выразим с помощью схемы примитивной рекурсии:

Итак, в предположении справедливости формулы (2) доказана формула (3). На основании метода математической индукции утверждаем, что предположении (1) справедливо для всех .

Ответ: .

Операция минимизации (поиск наименьшего корня). Если дана (n + 1)-местная функция f(x₁; x₂; ... x_n; у), то значение n-местной функции (x₁; x₂; ... x_n) можно определить, придавая вспомогательному аргументу у последовательно значения 0; 1; 2; 3; ..., пока не окажется, что функция f (x₁; x₂; ... x_n; у) в первый раз стала равной нулю, т.е. f(x₁; x₂; ... x_n; у) = 0. Полученное значение вспомогательного аргумента у принять за значение определяемой функции, соответствующей заданным значениям независимых переменных аргумента (x₁ = a₁; x₂ =a₂; ... x_n = a_n), при которых выполнялся вычислительный процесс.

Поиск значений функции  (x₁; x₂; ... x_n) может быть задан с помощью -оператора, который может быть записан так:

 (x₁; x₂; ... x_n) = _y (f (x₁; x₂; ... x_n; y) = 0.

Операция минимизации по i-ой переменной функции обозначается и определяется следующим образом:

Рассмотрим соотношение

, (*)

которое будем рассматривать как уравнение относительно y. Это уравнение будем решать подбором, подставляя вместо y числа 0, 1, 2 и т.д. Возможны случаи:

1) на некотором шаге левая часть соотношения (*) не определена. В этом случае считаем, что на наборе операция минимизации не определена;

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

3) левая часть соотношения (*) определена при …, но при равенство (*) не выполняется, а при оно выполняется. В этом случае число z считается значением операции минимизации на наборе .

Пример. Найти функции, получаемые из числовой функции с помощью операции минимизации по каждой ее переменной.

Решение.

1. Минимизируем данную функцию по переменной . Рассмотрим уравнение . (4)

а) Если , то при подстановке вместо y нуля получаем верное равенство.

б) Если , , то при подстановке в уравнение (4) вместо y единицы в левой части уравнения (4) появляется неосмысленное выражение – дробь , значит, в этом случае операция минимизации не определена.

в) Если , но , уравнение (4) примет вид . Это уравнение не может выполниться ни при каких .

г) Если , но , то при уравнение (4) выполнится.

Итак,

2. Минимизируем данную функцию по переменной . Рассмотрим уравнение . (5)

Если , а , то уравнение (5) примет вид и имеем решением число .

Если , то на самом первом шаге, при подстановке вместо y нуля, в левой части уравнения (5) возникает отрицательное число, т.е. неосмысленное выражение.

Итак,

3. Минимизируем данную функцию по переменной . Рассмотрим уравнение . (6)

Это уравнение на самом первом шаге, при подстановке вместо y нуля теряет смысл, операция минимизации по переменной нигде не определена.

4. Минимизируем данную функцию по переменной . Рассмотрим уравнение . (7)

Если набор переменных таков, что левая часть уравнения (7) имеет смысл и уравнение выполнимо, то можно считать, что оно выполнимо при подстановке в (7) переменной y на самом первом шаге, т.е. при y=0.

В остальных случаях значение операции минимизации не определено. Итак,

Использование оператора _y-удобное средство для поиска обратных рекурсивных функций.

Как правило, область определения функции  (x₁; x₂; ... x_n) меньше области определения функции f (x₁; x₂; ... x_n; у), что позволяет утверждать о частичной рекурсивности функции (x₁; x₂; ... x_n).

Пример. Пусть f (x₁; x₂; ... x_n; у) = f (x; у) = y² – x.

Тогда  (x) = _y ( (x; y) = y² –x = 0 или  (x) =y = .

Так как  (x) является рекурсивной функцией, то должен иметь только целое положительное значение. Таким образом,  (x) определена только для значения х = 1, 4, 9, 16... и имеет значение, соответственно, 1, 2, 3, 4, ... Таким образом, функция  (x) также является частично рекурсивной.

Если дан алгоритм вычисления функции f (a₁; a₂; ... a_n; у), то значение функции  (a₁; a₂; ... a_n) вычисляется следующим образом:

шаг 1: принять у = 0 и вычислить значение функции f (a₁; a₂; ... a_n; у).

шаг 2: если f (a₁; a₂; ... a_n; у) = 0, то конец, значение функции  (a₁; a₂; ... a_n) = у, иначе принять у = у + 1 и перейти к шагу 1.

Пример. Пусть f (a₁; a₂; ... a_n; у)=(x₁ – x₂ – x₃ – y), где x₁ = 7, x₂ = 1, x_з = 2.

Тогда по алгоритму минимизации имеем:

f =(7; 1; 2; 0) = 7 – 1 – 2 – 0  0;

f = (7; 1; 2; 1) = 7 – 1 – 2 – 1  0;

f = (7; 1; 2; 2) = 7 – 1 – 2 – 2  0;

f = (7; 1; 2; 3) = 7 – 1 – 2 – 3  0;

f = (7; 1; 2; 4) = 7 – 1 – 2 – 4 = 0.

Следовательно,  (x₁; x₂; ... x_n) =  (7; 1; 2) = 4.

Операция итерации. Повторное выполнение какого-либо процесса до тех пор, пока не будет удовлетворено заданное условие, называют итерацией. При этом выполнение процесса производится каждый раз полностью. Однократное выполнение процесса называют шагом итерации.