на главную страницу

L55_12  Рекурсия степенной  функции n^k

φ(1)=а

φ(n+1)=Ψ(φ(n),n)

Например, пусть дана функция ρ(n)=1*2*3*…*n. Тогда ρ(1)=1, ρ(n+1)=ρ(n)*n.

Т.о.,  мы имеем дело с процессом. Разница с обычным заданием очевидна, так как функция  ρ(n)=n! При обычном задании мы просто берем ряд чисел 1,2,…,n  и перемножаем их. Тогда как при рекурсивном определении мы осуществляем процесс вычисления каждого  значения  функции от аргумента n на основании использования значения функции от аргумента n-1 и аргумента n.

Мы имеем дело с последовательностью шагов, то есть аргументов, в качестве которых выступают числа натурального ряда, начиная с единицы и последовательно далее.  Например, пусть n=5 и φ(1)=а. Тогда φ(4+1)=Ψ(φ(4),4)  -φ(3+1)=Ψ(φ(3),3)-φ(2+1)=Ψ(φ(2),2) -φ(1+1)=Ψ(φ(1),1)-φ(1)=Ψ(φ(1),a). (ср. Гильберт, Бернайс,  "Основания математики" т.1 стр 52-53)

Но очевидно, что всё это - простое предписание. И если нам задана функция φ, то нам еще нужно определить функцию Ψ, а как раз об этом существенном вопросе  определение рекурсии нам ничего и не говорит, что понятно, так как для для разных видов функций  функция Ψ будет различной. Пусть, например, на задана функция φ(n)=n². ΨТогда Ψ  φ(1)=1. А как в этом случае будет выглядеть функция Ψ? Для ответа на этот вопрос построим таблицу, которой отражается общий закон изменения значений функции при приращении n на единицу:

   (n+1)² -n² =n²  +2n+1-n²=2n+1 Что представляет собой выражение 2n+1. Если n=1, то 2*1+1=3, где 3 это приращение, то есть число элементов, которые принадлежат единице на месте, обозначаемом числом 2. Число же у=4 соответствует сумме двух единиц х, такой, что для первой  из них у принимает значение 1, а для второй - значение 3. Если х равно сумме двух единиц, первой и второй, то третьей единице х будет соответствовать число единиц у=2*2+1=5 плюс сумма значений у для первых двух единиц, =4, итого, получаем, что единице х=3 соответствует пять единиц у=5, а сумма всех единиц будет равна 9. Т.о., мы получаем значение выражения 2n+1. Если будем различать числа порядка и количества т.о., что число, указывающее на место единицы в ряду единиц, будем обозначать буквой п  русского алфавита, а количественные числа, обозначающие сумму единиц буквой к, то получим у_к=n², а у_п=  2n+1 - количество единиц у, которые соответствуют х, находящейся на месте n.  Технологически это означает, что для того, чтобы определить количество единиц у, которые соответствуют элементу х на месте n+1, мы должны взять 2n+1. Т.о., имеем формулу: у_{п, n+1}=2n+1

Мы видим,  что 7=2*3+1,  5=2*2+1, 3=2*1+1, но во всех произведениях сомножители 1,2,3 - это значения n? Ψто есть Ψ2n+1Ψ Поэтому получаем функцию Ψ=n² +(1+2n) или φ(n+1)=n²+2n+1, и теперь мы можем обеспечить последовательное вычисление функции:

n	φ(n)=n2 2	φ(n+1)=n2+2n+1
1	1	1+(1+2*1)=4
2	4	4+(1+2*2)=9
3	9	9+(1+2*3)=16
4	16	Табл. 2

Обобщая принцип, заложенный в таблице 1, получаем формулу выражения функции от аргумента n+1 через значения аргумента n Ψдля функцииΨ φ(n+1)=(n+1)³ =n³+3n2+3n+1.  Но перед нами возникает вопрос, как можно получить эту формулу, исходя из приёма, представленного таблицей 1.

Ψ

Для этой цели рассмотрим таблицу 3  разностей для функции n³

Ψ

a	b	c	d	e	f
n	n3	(n+1)3 - n3	(n)3 -( n-1)3		Табл.3
5	125
		61
4	64		24
		37		6
3	27		18		0
		19		6
2	8		12
		7
1	1

В таблице 4 мы видим, что коэффициенты при постоянной 6 подчиняются закону, представленному таблицей Ψ 5Ψ, и эти коэффициенты представляют собой сумму натурального ряда n, которая равна  s=(n(n+1))/2

и т.о. получаем формулу (n+1)³ =n³ +6n(n+1)/2+1=n³ +3n³ +3n+1

Однако способ, каким получен результат, не соответствует методу  разностей, представленному  таблицей 3. А нам нужно найти общий способ  перехода от разностей к формуле. В конечном счете для любой степени числа, определяя последовательность разностей до тех пор, пока все они не начнут давать постоянное число, мы затем должны  идти от этой постоянной к переменным разностям. Так, в данном случае от постоянной 6 мы можем перейти к разностям 24 и 18 в соответствии с формулой 6n. Но точно также, как мы использовали постоянную 6 для определения разностей, точно также формулу 6n мы можем использовать для получения последующих разностей.  При меняя эту формулу, мы должны иметь возможность получения разностей 61, 37, 19. Итак, у нас есть формула 6n, которая обязательно будет частью формулы, обеспечивающей последующую разность, причем, в этой разности обязательно будет в том или ином виде присутствовать в качестве сомножителя еще одно n с чем-то еще.  И это будет произведением. И точно также, как к постоянной 6 мы сделали добавок в виде сомножителя n, мы должны по отношению к формуле 6n добавить сомножитель с тем, чтобы были получены нужные нам разности.  Если мы возьмём n+1 в качестве сомножителя, то, если обозначим разность числом  k, то 6n(n+1)+2=2k, откуда k=3n(n+1)+1=3n2+3n+1. Т.о., мы получили разность между двумя степенями (n+1)3-n3=3n2+3n+1, откуда получаем (n+1)3=n3+3n2+3n+1.

 Общий принцип определения разностей мы нашли, однако он слишком размыт и неопределенен для того, чтобы он был успешен для последующих степеней n.

Из выражения  (n+1)^x , где n, х принимают значения  из натурального ряда чисел, непосредственно следует его рекурсия. Именно, если x=0, то (n+1)0=1, если  х=1, то (n+1)1=n+1 и, соответственно,  (n+1)x+1=nx(n+1). Мы получаем рекурсивный ряд: (n+1)0=1;  (n+1)1=n+1; (n+1)2=n2+2n+1; (n+1)3=(n2+2n+1)(n+1)=n3+3n2+3n+1; (n+1)4=(n3+3n2+3n+1)(n+1)=n4+4n3+6n2+4n+1; (n+1)5=(n4+4n3+6n2+4n+1)(n+1)=n5+5n4+10n3+10n2 +5n+1.

Запишем полученные значения для различных х (табл.8).

   Каждая из строк таблицы  характеризуется пошаговым уменьшением показателя степени при n до единицы. Коэффициенты при n сначала увеличиваются до середины, а затем синхронно в том же порядке и значениях  уменьшаются, что соответствует треугольнику Паскаля, и отсюда делаем вывод,  что, имея дело   с биномом Ньютона, мы не осознавали этого,  и раз  мы это, наконец, осознали, поскольку всё же лучше поздно, чем никогда, то для любого значения х мы можем записать функцию Ψ(φ(n),n), обеспечивающую выражение φ(n+1) через φ(n).Отметим также, что коэффициенты при первом и последнем члене всегда равны 1, а при втором и предпоследнем равны значению показателя n в формуле (а+b)ⁿ

В биноме Ньютона  (a+b)n  коэффициенты не зависят от параметров а,b, но только от значений n. Показатель n последовательно  изменяется от n до единицы. Т.о., число  элементов равно n+1, так как n - это показатель степени, а 1 соответствует нулевому показателю степени. Например, если n=4, то мы имеем 5 элементов, каждому из которых можем дать имена а,б,с,д,е для их различения. Элементы как представители количества различаются только как различные,  и не более того , поэтому можно говорить о сочетаниях из 4 элементов по 4, по 3, по 2, по одному, по нолю, то есть о сочетаниях из n элементов по  m: Cmn=n!/(m!(n-m)!) Число членов в биноме равно n+1, так как, как выше сказано,  значения степеней изменяются от n до ноля. Поэтому в формуле (n+1)x, в силу того, что второй член в биноме равен единице и поэтому в качестве сомножителя на произведение не влияет, то, например,  если х=7, то получаем члены  nn7 + n6 + n5 + n4 + n3 + n2 + n +1 без коэффициентов И теперь нам остается рассчитать коэффициенты в соответствии с формулой для сочетаний из 7 элементов по 7,6,5,4,3,2,1,0 элементов.  Получаем для 7 из 7 - 1,  для 6 из 7 - 7, для 7 из 5 - 21, для 7 из 4 - 35, для  7 из 3 - 35, для 7 из 2 - 21, для 7 из 1- 7, для 7 из 0 - 1 и окончательно (n+1))7 =  n7 + 7n6 +21 n5 + 35n4 +35 n3 +21 n2 +7n +1
    Итак, мы научились определять для функции вида n^x для любого натурального значения x и для любого натурального значения n функцию φ(n+1)=Ψ(φ(n),n), однако принципа перехода от метода разностей к рекурсивному определению для любого натурального х как не было, так и нет. Тем не менее, так как мы можем это делать посредством бинома Ньютона и так как рекурсия оказывается частным случаем  бинома, то точно также, как для степеней 2,3 мы совершили переход от разностей к биному, точно также возможен и обратный переход от бинома к разностям для степеней, больших 3. Закономерности, связанные с этим, могут представлять методологический интерес в силу наглядности метода разностей.

    09.12.12 г.