Штыров Валерий Яковлевич : другие произведения.

Рекурсия степенной функции

Самиздат: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Ссылки:


 Ваша оценка:

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

Принцип рекурсивных определений состоит в том, что всякое последующее значение функции определяется на основе предыдущего. Поэтому должно быть вычислено значение функции для некоторого начального значения аргумента. Пусть в качестве задатчика последовательности аргументов выступает натуральный ряд чисел. Тогда, определив значение функции для 1, мы затем можем последовательно определить значение функции для любого значения аргумента n. Аналитически это выражается в виде

φ(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)=n2. ΨТогда Ψ  φ(1)=1. А как в этом случае будет выглядеть функция Ψ? Для ответа на этот вопрос построим таблицу, которой отражается общий закон изменения значений функции при приращении n на единицу:

n

n2

(n+1)2-n2

 

 

4

16

 

 

 

 

 

7

 

 

3

9

 

2

 

 

 

5

 

0

2

4

 

2

 

 

 

3

 

 

1

1

 

 

Табл. 1

 

n*2 +1

(n+1)*2-1

Табл. 1а

3*2+1

4*2-1

7

2*2+1

3*2-1

5

1*2+1

2*2-1

3

 

 

1

4

6*6+1=37

3

3

1

3*6+1=19

2

2

 

1*6+1=7

1

 

 

 

 

 

  Табл. 4

 

 

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

ΨΨ

n

1

2

3

4

5

6

Табл. 5

s

 

3

6

10

15

21

 

 

и т.о. получаем формулу (n+1)3 =n3 +6n(n+1)/2+1=n3 +3n3 +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).

x

 

 

 

 

 

 

 

 

 

 

Табл.6

0

 

 

 

 

 

1

 

 

 

 

 

1

 

 

 

 

1

 

1

                                  

 

 

 

2

 

 

 

n2

 

2n

 

1

 

 

 

3

 

 

n3

 

3n2

 

3n

 

1

 

 

4

 

n4

 

4n3

 

6n2

 

4n

 

1

 

5

n5

 

5n4

 

10n3

 

10n2

 

5n

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

В биноме Ньютона  (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
    Итак, мы научились определять для функции вида nx для любого натурального значения x и для любого натурального значения n функцию φ(n+1)=Ψ(φ(n),n), однако принципа перехода от метода разностей к рекурсивному определению для любого натурального х как не было, так и нет. Тем не менее, так как мы можем это делать посредством бинома Ньютона и так как рекурсия оказывается частным случаем  бинома, то точно также, как для степеней 2,3 мы совершили переход от разностей к биному, точно также возможен и обратный переход от бинома к разностям для степеней, больших 3. Закономерности, связанные с этим, могут представлять методологический интерес в силу наглядности метода разностей.


    09.12.12 г.


 Ваша оценка:

Связаться с программистом сайта.

Новые книги авторов СИ, вышедшие из печати:
О.Болдырева "Крадуш. Чужие души" М.Николаев "Вторжение на Землю"

Как попасть в этoт список

Кожевенное мастерство | Сайт "Художники" | Доска об'явлений "Книги"