close

Вход

Забыли?

вход по аккаунту

(Срок сдачи: 25 ноября 2014 г.). - math-info

код для вставкиСкачать
НИУ ВШЭ, 2014-15, «Дискретная математика»
Отделение лингвистики, 2014-15 уч. год
Дискретная математика
(11 ноября 2014 г.)
Н. Е. Сахарова, Ю. Г. Кудряшов, И. В. Щуров
Дополнительное домашнее задание 3 (Срок сдачи: 25 ноября 2014 г.).
Фамилия и имя студента:
Напоминаем, что гораздо лучше вообще не сдавать задание или сдать частично сделанное задание, чем сдать хотя бы частично списанный текст. Списанное домашнее задание (или списанное
частично) оценивается в 0 баллов.
Прежде чем приступать к оформлению решения, пожалуйста, напишите на каждой странице в
правом верхнем углу свою фамилию, имя и отчество. Не забудьте, что итоговый файл Вам необходимо отправить по адресу dm.ling.hse.teachers(собака)gmail.com с темой письма «Дополнительное
ДЗ 3, Фамилия Имя». Задания принимаются до 23 часов 59 минут московского времени, 25 ноября
(воскресение). Формат файла pdf.
Задача 1. Числа Фибоначчи — это последовательность целых чисел { }, заданная с помощью
соотношения (или рекуррентной формулы):
0 = 0,
1 = 1,
+1 =  + −1
(иными словами, каждое следующее число в последовательности Фибоначчи равно сумме двух
предыдущих чисел).
Последовательность чисел Фибоначчи начинается так:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233.
Используя метод математической индукции, докажите следующие свойства чисел Фибоначчи:
a) 1 + 2 + ... +  = +2 − 1;
b) 2 + 4 + ... + 2 = 2+1 − 1;
c) 12 + 22 + ... + 2 =  +1 ;
d) (формула Бине) Докажите по индукции явную формулу для вычисления чисел Фибоначчи:
 =
 − ¯
√
,
5
где число  = 1+2 5 называется золотым сечением, а ¯ = 1−2 5 . *Указание: вспомните про реккурентное соотношение для чисел Фибоначчи +1 =  + −1 .
Задача 2. (Или продолжение задачи 3 из первого дополнительного задания)
a) Докажите по индукции равенство:
√
√
1
2
3
0 + −1
+ −2
+ −3
+ . . . = +1 ;
(сумму чисел, стоящих слева от знака равенства, можно интерпретировать как сумму элементов
треугольника Паскаля, стоящих на одной диагонали);
b) Докажите, что число слов длины  − 1 в алфавите из двух букв ( и  ), таких, что никакие
две буквы  не стоят рядом, равно +1 .
Задача 3. На столе лежат  ( > 3) мешочков с сахаром. Первый мешочек весит 1 кг., второй 2
кг., третий 3 кг., и. т. д, последний весит  кг. При каких значениях  все мешочки на столе можно
разложить на три кучки одинакового веса?
Н. Е. Сахарова, Ю. Г. Кудряшов, И. В. Щуров
1
1/--страниц
Пожаловаться на содержимое документа