С.Н. Селезнева - Основы дискретной математики (1060725), страница 9
Текст из файла (страница 9)
Найти общее решение следующих линейных неоднородныхрекуррентных уравнений:1)2)3)4)xn − xn−1 = 3;xn − 5xn−1 = 6;xn + 3xn−1 = 3n − 4;xn − 5xn−1 + 6xn−2 = 3 · 2n−1 ;5)6)7)8)xn − xn−1 − 6xn−2 = (2n + 5) · 3n ;xn − 3xn−1 + 3xn−2 − xn−3 = 3 · 2n ;xn − 7xn−1 + 15xn−2 − 9xn−3 = 3n−1 ;xn − xn−1 − 3xn−2 + 3xn−3 = −10.Задача 4.4. Решить следующие линейные неоднородные рекуррентныеуравнения:1)2)3)4)5)6)7)8)xn − 3xn−1 = 2 · 3n , x1 = 9;xn − xn−1 = 2n√− 2, x1 = 1;xn − 2xn−2 = ( 2)n+2 , x1 = 0, x2 = 6;xn − xn−1 − 12xn−2 = 7 · 4n−1 , x1 = −2, x2 = 50;xn − 2xn−1 + xn−2 = (n − 2) · 2n−2 , x1 = 5, x2 = 9;xn − 6xn−1 + 12xn−2 − 8xn−3 = 1, x1 = −3, x2 = −5, x3 = 7;xn − 2xn−1 − 5xn−2 + 6xn−3 = −4(3n + 8), x1 = 2, x2 = 10, x3 = 15;xn − xn−3 = n2 − 3n + 1, x1 = 91 , x2 = 89 , x3 = 5.51Задача 4.5. Найти явное выражение элементов последовательности Фибоначчи15 {fn }, которая задается условиями: f1 = f2 = 1, fn = fn−1 +fn−2 .Задача 4.6.
Доказать, что арифметическая прогрессия является возвратной последовательностью. Построить рекуррентное уравнение, задающее арифметическую прогрессию с первым членом a1 и разностью d.Задача 4.7. Доказать, что геометрическая прогрессия является возвратной последовательностью. Построить рекуррентное уравнение, задающее геометрическую прогрессию с первым членом b1 и знаменателем q.Задача 4.8. 1. Доказать, что следующие последовательности являютсявозвратными:1) xn = n;2) xn = n2 ;3) xn = n3 ;4) xn = n4 .Найти задающие их рекуррентные уравнения.2.
Доказать, что последовательность xn = nk , где k ≥ 1 – натуральноечисло, является возвратной. Найти задающее ее рекуррентное уравнение.15Фибоначчи, или Леонардо Пизанский (Fibonacci) – итальянский математик XII-XIII веков.525ОтветыК разделу 1.21.4 1) x ∈/ A, или x ∈/ B, или x ∈ C; 2) x ∈/ A, B, x ∈ C; 3) x ∈/ A,или x ∈ B, или x ∈/ C; 4) x ∈/ A, C или x ∈ B, x ∈/ C; 5) x ∈ A, B, C;6) x ∈ A, B или x ∈ A, C; 7) x ∈/ A, B или x ∈/ C; 8) x ∈/ A, x ∈ C илиx∈/ B, x ∈ C.1.6 1) то B ⊆ A; 2) то A ⊆ B; 3) то A ∩ B = ∅; 4) верно, если B ⊆ A;5) верно, если B ⊆ A; 6) верно, если A = ∅; 7) верно, если B = C;8) верно, если B = C.1.7 1) A∩C; 2) A∩D; 3) D ∩B; 4) A∩C ∩D; 5) D ∩(A∪B)); 6) B ∩A∩C;7) C ∩ (A ∪ D); 8) B ∩ A ∩ D ∩ C.1.9 4.
1) множество пар натуральных чисел; 2) координатная плоскость;3) ось ординат; 4) полоса на координатной плоскости между прямымиy = 0 и y = 1, содержащая их.1.11 1) да; 2) нет; 3) нет; 4) нет.К разделу 1.41.12 332 .9P1.13 2 ·k 2 + 102 = 670.k=11.14 5.nn−11.15 1) 2n ; 2) 2n−1 ; 3) 2n−2 ; 4) 2n−2 ; 5) 2 2 , если n – четно, 2 · 2 2 , еслиn – нечетно; 6) 2n−1 ; 7) 2n−1 ; 8) 2n − 2.1.16 1) 3k ; 2) 3k ; 3) 1; 4) 0.1.17 1) 2k ; 2) 2k ; 3) 5k ; 4) 1; 5) 3k ; 6) 1; 7) 3k ; 8) 1.1.18 1) 3k ; 2) 3k .1.19 1. 1) да, да, да, да; 2) да, да, нет, нет; 3) да, да, да, да; 4) да, нет,да, нет; 2. 1) n, n = 0, 1, .
. .; 2)n2 , n = 0, 1, . . .; 3) n, n = 0, 1, . . .; 4) 2n,n = 0, 1, . . ..1.21 n − (m1 + 1)(m2 + 1) . . . (mk + 1).К разделу 1.61.24 190.1.25 1) 3 · 2n−2 при n ≥ 2; 2) 2n−3 при n ≥ 3; 3) 13 · 2n−4 ; 4) 9 · 2n−4 ;5) 5 · 2n−4 ; 6) 3 · 2n−4 ; 7) 7 · 2n−4 ; 8) 3 · 2n−4 (в 3)-8) при n ≥ 4).kPPn1.26 2. 42; 3. 166; 4. 77; 5.
878; 6. 25; 7.(−1)j−1 b pi ·...·pc;ij=1 1≤i1 <...<ij ≤k531j8. (k − 1)+kPPj=0 1≤i1 <...<ij ≤k(−1)j b pi1n·...·pij c.1.27 20.1.28 1) 20; 2) 80; 3) 60; 4) 40.К разделу 1.81.30 1. 3; 2. 2; 3. 4; 4. 5.1.31 1) 4; 2) 11; 3) 22; 4) 12.1.32 2.
да.1.37 нет.1.38 да.К разделу 2.232.2 C35= 6545.2.3 A23 = 6.442.4 1) C20= 4845; 2) C̄20= 8855; 3) A420 = 116280; 4) Ā420 = 160000.4572.5 C25· C25· C25.2.6 1. n!; 2. (n − 1)!2.7 1) 300 + 3002 + 3003 ; 2) 300 + 300 · 299 + 300 · 299 · 298.n!(n−1)!2.8 1) (n−1)!.2 ; 2)2nn−mP (−1)kP kkCm+k · (−1)2.11 1. n! ·;2.n!·k!k! .2.122.13k=0k=01930 (см.
задачу 2.11).3 1 118 , 3 , 4 , 0, 24 (см. задачу 2.11).nP2.14 1. (n)k ; 2.(n)k .k=12.15 n + 1.2.16 1. C̄kn ; 2. 1) C̄32 = 6; 2) C̄33 = 10; 3) C̄42 = 10; 4) C̄45 = 56.К разделу 3.23.1 1. 1) да; 2) нет; 3) да; 4) да; 2. 1) да; 2) да; 3) да; 4) нет.3.2 1) да; 2) да; 3) нет; 4) нет.3.3 1) да; 2) нет; 3) да; 4) нет.3.4 1. 1) рефлексивно, симметрично, транзитивно; 2) иррефлексивно,транзитивно; 3) иррефлексивно, симметрично; 4) рефлексивно, симметрично, транзитивно; 2.
1) иррефлексивно; 2) иррефлексивно, транзитивно; 3) рефлексивно, симметрично, транзитивно; 4) симметрично.3.5 1) (a1 , . . . , an ) ≤ (b1 , . . . , bn ), если a1 ≤ b1 , . . . , an ≤ bn ; 2) расположение слов не более, чем из n букв, по алфавиту.5423.7 1) 2k ; 2) 2k .К разделу 3.43.8 1) да; 2) да; 3) да; 4) нет.3.9 1) да; 2) нет.3.10 1) нет; 2) да.3.11 1) да; 2) да; 3) да; 4) нет.3.12 1) да; 2) нет.3.13 1) нет; 2) да.3.14 1) да; 2) да; 3) нет, не рефлексивно; 4) да.3.15 1) нет; 2) да; 3) нет; 4) да.К разделу 3.63.16 1) да, линейный; 2) да, частичный.3.17 1) да, линейный; 2) нет.3.18 1) да; 2) да; 3) нет; 4) да.3.19 1) да, линейный; 2) нет.3.20 1) да, частичный; 2) нет.3.21 1) да, наименьший (1, 1), наибольший (3, 3); 2) нет, не антисимметрично; 3) да, наименьший (1, 1), наибольший (3, 3); 4) да, минимальные(1, 1), (2, 2), (3, 3), максимальные (1, 3), (3, 1).К разделу 3.83.26 1.
1) 2; 2) 3; 3) 2; 4) 4.3.27 1. 1) 4; 2) 7; 3) 9; 4) 22; 2. 1) (101); 2) (0101); 3) (1100); 4) (10101).3.29 1. n; 2. Cnd .3.34 3. 1) 2r ; 2) Cnr · 2r ; 4. 3n .К разделу 4.24.1 1) C1 ·2n ; 2) (C1 +C2 n)·2n ; 3) C1 ·(−1)n +C2 ·(−2)n ; 4) C1 ·(−4)n +C2 ·3n ;5) C1 · 2n + C2 , если n√– кратно трем,C1 · 2n − C2 , если n – не кратно√√трем; 6) C1 + C2 · (− 2)n + C3 · ( 2)n ; 7) (C1 + C2 n + C3 n2 ) · ( 3)n ;8) C1 + C2 · 2n + C3 · 3n .4.2 1) 5 · 3n ; 2) (−2)n + 1; 3) (3n + 1) · 2n ; 4) 3n−1 + 2n−1 , 5) 2n−2 + 1 + (−1)n ;6) n2 − n + 1; 7) (2n + 1) · 2n + (−1)n ; 8) 2, если n кратно трем, и 0, еслиn не кратно трем.4.3 1) C1 + 3n; 2) C1 · 5n − 23 ; 3) C1· (−3)n + −1 + 43 n ; 4) (C1 − 3n) ·n2n2n + C2 · 3n ; 5) C1 · (−2)n + C2 + 13 n · 3√; 6) (C1 + C√2 n + C3 n ) + 24 · 2 ;7) C1 + (C2 + C3 n + 14 n2 ) · 3n ; 8) C1 · (− 3)n + C2 · ( 3)n + C3 + 5n.55√√4.4 1) (2n + 1) · 3n ; 2) n2 − n + 1; 3) (− 2)n + n · ( 2)n ; 4) 2 · (−3)n + n · 4n ;5) (1 + 2n) + n · 2n ; 6) (1 − 3n + n2 ) · 2n − 1; 7) 1 − (−2)n−1 + 3n−1 + n2 ;1 3n3 , если8) 2 + 91 n кратнотрем, и 9 n , если n не кратно трем.√n√n1+ 54.5 √15.− 1−2 524.6 xn − 2xn−1 + xn−2 = 0, x1 = a1 , x2 = a1 + d.4.7 xn − qxn−1 = 0, x1 = b1 .4.8 1.
1) xn − 2xn−1 + xn−2 = 0; 2) xn − 3xn−1 + 3xn−2 − xn−3 = 0; 3)xn − 4xn−1 + 6xn−2 − 4xn−3 + xn−4 = 0; 4) xn − 5xn−1 + 10xn−2 − 10xn−3 +k+1Pjxn−j = 0.5xn−4 − xn−5 = 0; 2. xn − (−1)j−1 Ck+1j=1566Литература1. Архипов Г.И., Садовничий В.А., Чубариков В.Н. Лекции по математическому анализу. Лекция 1. Множества. – М.: Издательство МГУ,1995, 172 с.2. Гаврилов Г.П., Сапоженко А.А.
Задачи и упражнения по дискретной математике. – М.: Физматлит, 2004, 416 с.3. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. – М.: МЦНМО, 2002,128 с.4. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука, 1984, 223 с.5. Матросов В.Л., Стеценко В.А. Лекции по дискретной математике. –М.: МГПУ, Прометей, 1997, 219 с.6. Редькин Н.П.
Дискретная математика. – СПб., М., Краснодар: Лань,2006, 96 с.7. Яблонский С.В. Введение в дискретную математику. – М.: Высшаяшкола, 2001, 384 с.57Содержание1 Элементы теории множеств1.1 Основные понятия . . . . . . . . . . . . . . .1.2 Упражнения . . . . . . . .
. . . . . . . . . .1.3 Конечные множества. Мощность множества1.4 Упражнения . . . . . . . . . . . . . . . . . .1.5 Формула включений-исключений . . . . . . .1.6 Упражнения . . . . . . . . . . . . . . . . . .1.7 Принцип Дирихле . . . . . . . . . . . . . . .1.8 Упражнения . . . . .
. . . . . . . . . . . . .2 Элементы комбинаторики2.1 Комбинаторные объекты . . .2.2 Упражнения . . . . . . . . . .2.3 Свойства комбинаторных чисел2.4 Упражнения . . . . . . . . . .....3 Отношения на множествах3.1 Основные понятия . . . . . . . .3.2 Упражнения . . . . . . . . . . .3.3 Отношение эквивалентности . .3.4 Упражнения . . . . . . . . . . .3.5 Отношение частичного порядка .3.6 Упражнения . . .
. . . . . . . .3.7 Булев куб . . . . . . . . . . . . .3.8 Упражнения . . . . . . . . . . .........................................................................................................................................................................................................................................448111417172020....2323252829........3232333536374042444 Последовательности474.1 Возвратные последовательности . .
. . . . . . . . . . . . . 474.2 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . 515 Ответы536 Литература5758СЕЛЕЗНЕВА Светлана НиколаевнаОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИУчебное пособиеЭлектронный адрес автора:e-mail: selezn@cs.msu.suИздательский отделфакультета вычислительной математики и кибернетикиМГУ имени М.В. ЛомоносоваЛицензия ИД N 05899 от 24.09.01 г.119992, ГСП-2, Москва, Ленинские горы, МГУ имени М.В.
Ломоносова,2-й учебный корпус59.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
