Реферат: Дискретная математика 3

U(x)=Þ

Итак, .

§11. Числа Фибоначчи.

Последовательность Фибоначчи задается рекуррентным соотношением u_{n +2} =u_{n +1} +u_n , u₀ =1, u₁ =1. То есть 1, 1, 2, 3, 5, 8, 13, 21, …. Найдем u_n .

K(x)=1-x-x²

U(x)=

С(x)=K(x)×U(x)=u₀ +u₁ x+u₂ x² +…-u₀ x-u₁ x² -u₂ x³ -…-u₀ x² -u₁ x³ -u₂ x⁴ -…=

=u₀ +u₁ x-u₀ x=1+x-x=1

F(x)=x² -x-1=

K(x)=

U(x)==

.

ÞÞ

Þ B=, A=1-B=.

U(x)=×+×=

=+.

u_n =×+×=

=.

Покажем, что u_n и u_{n +1} – взаимно простые числа. Воспользуемся методом математической индукции.

База индукции. (u₀ , u₁ )=1, выполняется.

Индукционное предположение. Допустим, что (u_{n -1} , u_n )=1.

Шаг индукции. Докажем, что (u_n , u_{n +1} )=1.

Действительно, если предположить, что (u_{n +1} , u_n )=d>1, то получаем u_{n +1} ∶d и u_n ∶d, но u_{n +1} =u_n +u_{n -1} . Два члена последнего равенства делятся на d, а значит, и третий член u_{n -1} должен делится на d. Следовательно, (u_n , u_{n -1} )=d. Получили противоречие с индукционным предположением. Значит, (u_n , u_n+1 )=1.

Введение в теорию графов

Множество самых разнообразных задач естественно формулируется в терминах точек и связей между ними, то есть в терминах графов.

Первой работой теории графов, как математической дисциплины, считают статью Эйлера (1736 г.), в которой рассматривалась задача о Кенигсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз.

С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом