Вопросы и упражнения для самостоятельной работы
Найти производящую функцию следующей последовательности
ak = 
Найти производящую функцию следующей последовательности
ak = 
Найти производящую функцию следующей последовательности
ak = 
Найти производящую функцию последовательностиak = 3k,k = 0, 1, … .
Найти производящую функцию последовательности ak = 3kk,k = 0, 1, … .
Найти производящую функцию следующей последовательности:
ak = 
Найти производящую функцию следующей рекуррентной последовательности:
u0 = 3,u1 = 6,uk+2 = 2k+1 + 3uk .
Разложить в степенной ряд следующую производящую функцию:
f(z) = 
.
Для заданной рекуррентной последовательности
u0 = 1,uk+1 = 2uk+1 + k
найти производящую функцию и получить формулу общего члена последовательности.
Найти сумму
.
Найти сумму
.
Найти сумму
.
Найти сумму
,k m,n.
Найти сумму
k m < n.
Найти число целых решений уравнения
x1 + x2 + x3 + x4 = 18
при условии, что 0 xi 9,i = 1, 2, 3, 4.
Найти число целых решений уравнения
x1 + x2 + x3 + x4 + x5 + x6 = 30
при условии, что 0 xi 10,i = 1, 2, 3, 4.
Пустьpn – количество чисел, состоящих изnнечетных цифр, среди которых 1 и 3 встречаются хотя бы по одному разу. Составить производящую функцию последовательностиpnи найти формулу для вычисленияpn.
Найти число способов разместитьnпредметов по трем ящикам так, чтобы ни один ящик не был пустым.
§4.3. Числа Фибоначчи
Числа Фибоначчиобразуют последовательность, в которой первые два члена равны 0 и 1, а каждый следующий равен сумме двух предыдущих. В соответствии с определением числа Фибоначчи составляют последовательность
F0 = 0,F1 = 1,F2 = 1,F3 = 2,F4 = 3,F5 = 5,F6 = 8,…
такую, что
Fn+2 = Fn+1 + Fn.
Свойства чисел Фибоначчи
1)
для любогоn 0;
2) Fn+2Fn – 
= (–1)n+1.
3) Каждое целое положительное целое число nимеет единственное представление вида
n = 
,
где k1 k2 +2; k2 k3 +2; …, kr–1 kr +2; kr 2.
4) Производящая функция для последовательности чисел Фибоначчи имеет следующий вид:
F(z) = F0 + F1z + F2z2 + … = 
.
5) Имеют место следующие формулы Бине:
Fn = 
,
где
и
.
6) k+2=Fk+2+Fk+1для любогоk 0.
7) Число Фибоначчи Fnесть ближайшее целое к числу
.
8)
.
9)
.
10)
.
11)
при любомn 0.
Примеры
1.Доказать, что
FkFn+1+Fk–1Fn= Fn+k .
Решение. Проведем доказательство индукцией поk. Приk = 1 иk = 2 получаем верные равенства:
1Fn+1+ 0Fn= Fn+1 ;
1Fn+1+ 1Fn= Fn+2 ;
Выполним индуктивный шаг. Предполагая, что
FjFn+1+Fj–1Fn= Fn+j,
при всех j k, покажем, что
Fk+1Fn+1+FkFn= Fn+k+1 .
В самом деле, по индуктивному предположению
FkFn+1+Fk–1Fn= Fn+k
и
Fk–1Fn+1+Fk–2Fn= Fn+k–1 .
Складывая эти два равенства и учитывая, что Fk+Fk–1= Fk+1,
Fk–1+Fk–2= Fk, получаем доказываемое равенство.
2.Доказать, что
Fn+1=Fn+ n ,
где
и
.
Решение. По формулам Бине имеем:
Fn = 
,Fn+1 = 
,
откуда
Fn+1–Fn=
=n,
что и доказывает рассматриваемое равенство.
3.НайтиF15.
Решение. По формулам Бине имеем:
F30 = 
.
Так как || < 0,6,
то
< 10–3.
Значит,
< 10–3.
Поскольку
610,
аF30 – число
целое, получаемF15 = 610.
Вопросы и упражнения для самостоятельной работы
Доказать, что
(Fn)2+ (Fn+1)2= F2n+1.
Доказать, что
FnFn+1–Fn–2Fn–1= F2n–1 .
Доказать, что
Fn+1Fn+2–FnFn+3= (–1)n .
Доказать, что
(Fn)3+ (Fn+1)3= (Fn–1)3+ F3n.
Доказать, что
F0 + F2 + … + F2n = F2n+1.
Доказать, что
F1 + F3 + … + F2n+1 = F2n+2.
Доказать, что
F1 + F2 + … + Fn =Fn+2– 1.
Доказать, что
(F1)2+ (F2)2+ … + (Fn)2= FnFn+1.
НайтиF20.
Доказать, что Fn+60 – Fn делится на 10.
Найти суммуF3 + F6 + … + F3n.
Найти сумму (F1)3+ (F2)3+ … + (Fn)3.
Ответы