Теория чисел Фибоначчи (стр. 5 из 14)
а) оно имеет место для числа 1;
б) из справедливости доказываемого утверждения, для какого-либо произвольно – выбранного натурального числа № следует его справедливость для числа n+1.
Всякое индуктивное доказательство утверждения, справедливого для любого натурального числа, состоит, поэтому из двух частей.
В первой части устанавливается справедливость доказываемого утверждения для единицы, ее называют иногда основанием индукции. Во второй части доказательства делается предположение о справедливости доказываемого утверждения для некоторого произвольного (но фиксированного) числа № и из этого предположения, которое часто называют индуктивным предположением, выводится, что и для числа n+1 доказываемого утверждение имеет место.
Вторая часть доказательства называется индуктивным переходом. Иногда применяется индуктивное рассуждение, которое можно назвать переходом "от всех чисел, меньших n, к n". При этом необходимость в специальном доказательстве основания индукции отпадают, так как, говоря формально, доказательство для случая n+1 и есть переход от "всех" целых положительных чисел, меньших единицы (которых просто нет), к единице. Именно таким является доказательство возможности разложения любого натурального числа на простые множители.
Предположим, что каждое из чисел, меньших некоторого n, разложимо в произведение простых множителей.
Если число № оказывается простым, то оно само и является своим разложением.
Если же число № составное, то его по определению, можно представить в виде произведения хотя бы двух сомножителей: n=n1n2, где n1 ≠ 1 и n2 ≠ 1.
Но тогда n1>n и n2<n,а по индуктивному предположению как n1, так и n2 разлагаются на простые множители. Тем самым и № разложимо на простые множители.
6. Простейшей реализацией идеи индукции в применении к числам Фибоначчи является само определение чисел Фибоначчи. Оно состоит в указании двух первых чисел Фибоначчи: U1=1 и U2=1 и в индуктивном переходе от Un и Un+1 к Un+2, даваемым рекуррентным соотношением : Un+Un+1=Un+2.В частности, отсюда автоматически следует, что если некоторая последовательность чисел начинается с двух единиц, а каждое из следующих получается сложением двух предыдущих, то эта последовательность является последовательностью чисел Фибоначчи.
В качестве примера рассмотрим так называемую "задачу о прыгуне". Она состоит в следующем.
"Задача о прыгуне". Прыгун может прыгать в одном направлении вдоль разделенной на клетки полосы, перемещаясь при каждом прыжке либо в соседнюю клетку, либо через клетку. Сколькими способами может он сдвинуться на n-1 клетку и, в частности, переместиться из первой клетки в n-ю? (Способы прыганья считаются одинаковыми, если в ходе каждого из них прыгун побывает в одних и тех же клетках). Обозначим искомое число через хn. Очевидно х1=1(ибо переход из первой клетки в первую же осуществляется только одним способом-отсутствием прыжков) и х2=1 (переход из первой клетки во вторую также единствен: он состоит в одном непосредственном прыжке на соседнюю клетку). Пусть целью прыгуна является достижение n+2-й клетки. Общее число способов осуществление этой цели в наших обозначениях равно хn+2.Но с самого начала эти способы разбиваются на два класса: начинающиеся с прыжка во вторую клетку и начинающиеся с прыжка в третью клетку. Из второй клетки прыгун может переместиться в n+2-ю хn+1 способами, а из третьей хn способами.
Таким образом, последовательность чисел х1, х2,…, хn,…удовлетворяет рекуррентному соотношению:
xn+хn+1=хn+2 и поэтому совпадает с последовательностью чисел Фибоначчи хn=Un.
7. Докажем по индукции следующую важную формулу:
Un+m=Un-1Um+UnUm+1.(31)
Доказательство этой формулы будем вести индукцией по m.
При m=1 эта формула принимает вид:
Un+1=Un-1U1+UnU2, что очевидно.
При m=2 формула (31) также верна, потому что
Un+2=Un-1U2+UnU3=Un-1+2Un=Un-1+Un +Un=Un+1+Un.
Основание индукции, таким образом, доказано.
8.Полагая в формуле (31) m = n, мы получаем
U2n=Un-1Un+UnUn+1,
или
U2n=Un(Un-1+Un+1) (32)
Из написанного равенства видно, что U2n делится на Un.
Так как Un=Un+1-Un-1, формулу (32) можно переписать так:
U2n=(Un+1-Un-1) =(Un+1+Un-1), или
U2n= U2n+1-U 2n-1, т. е. разность квадратов двух чисел Фибоначчи, номера которых отличаются на два, есть снова число Фибоначчи (и причем с четным номером).
Аналогично(полагая m=2n) можно показать, что
U3n=U3n+1+U3n-U3n-1.
9.В дальнейшем нам пригодиться следующая формула:
U2n = Un-1Un+1+(-1)n+1 (33)
Докажем ее индукцией по n.
Для n=2, формула (33) принимает вид:
U22=U1U3-1,
что очевидно.
Предположим теперь в формулу (33) доказанной для некоторого n, прибавим к обеим частям ее по UnUn+1. Получим
U2n+UnUn+1= Un-1Un+1+ UnUn+1+(-1)n+1,
Или
Un (Un+Un+1)= Un+1(Un-1+Un)+(-1)n+1,
Или
Un Un+2= U2n+1+(-1)n+1,
Или
U2n+1= Un Un+2+(-1)n+2,
Этим индуктивный переход обоснован и формула (33) доказана для любого n.
10. Аналогичным способом можно установить такие свойства чисел Фибоначчи:
U1U2+U2U3+U3U4+…+U2n-1U2n=U22n.
U1U2+U2U3+U3U4+…+U2nU2n+1=U22n+1-1.
nU1+(n-1)U2+(n-2)U3+…+2Un-1+Un=Un+4-(n+3)
U1+2U2+3U3+…+nUm=nUn+2-Un+3+2
11. До сих пор мы определяли числа Фибоначчи рекуррентно, т. е. индуктивно, по их номеру. Оказывается, что любое число Фибоначчи можно определить и непосредственно, как некоторую функцию его номера.
Исследуем для этого различные последовательности U1, U2, U3, …., Un,…, удовлетворяющие соотношению
Un=Un-2+Un-1 (34)
Все такие последовательности мы будем называть решениями уравнения (34)
Будем обозначать буквами V,V`, V`` соответственно последовательности:
w1,w2,w3,…
w1`,w2`,w3`,…
w1``,w2``,w3``,…
Сначала докажем две леммы.
ЛЕММА 1.
Если V – есть решение уравнения (34), а c – произвольное число, то последовательность cV (т. е. последовательность cw1,cw2,cw3,…) есть так же решение уравнения (11)
ДОКАЗАТЕЛЬСТВО: Умножив соотношение wn=wn-2+wn-1 почленно на c, получаем cwn=cwn-2+cwn-1, а это и требовалось доказать.
ЛЕММА 2.
Если последовательности V`и V`` являются решениями уравнения (34), то и их сумма V`+ V`` (т. е. последовательность w`1+w``1, w2`+w2``, w3` +w3``) является решением уравнения (11)
ДОКАЗАТЕЛЬСТВО: Из условия леммы мы имеем:
w`n=w`n-2+w`n-1
и
w``n=w``n-2+w``n-1
Сложив эти два равенства почленно, получим:
w`n +w``n= (w`n-2+w``n-2)+(w`n-1+w``n-1).
Этим лемма доказана.
Из этих лемм также выводится знаменитая формула Бине:
Рассмотрим теперь некоторые свойства чисел Фибоначчи, касающиеся их делимости. Докажем следующую теорему.
ТЕОРЕМА. Если № делиться на m, то и Un делиться на Um.
ДОКАЗАТЕЛЬСТВО:
Пусть № делиться на m, т. е. № = mk. Будем вести доказательство индукцией по k.
Для k=1, № = m, так что в этом случае Un делиться на Um очевидным образом. Предположим теперь что Umk делиться на Um и рассмотрим Um(k+1). Тогда имеем: Um(k+1) = Umk+m и на основании формулы (31) получим:
Um(k+1) = Umk+m= Umk-1Um+ UmkUm+1
Первое слагаемое правой части написанного равенства, очевидно, делиться на Um. Второе же его слагаемое кратно Umk т. е. по индуктивному предположению тоже делиться на Um. Значит, на Um делиться и их сумма, т. е. Um(k+1). Теорема доказана.
Большой интерес представляет вопрос об арифметической природе чисел Фибоначчи, об их делителях.
Докажем, что при № составном и отличном от 4 Un есть составное число. Действительно, для такого № можно написать n=n1n2, где 1<n1<n,
1<n2<n, либо n1>2, либо n2>2. Пусть для определенности n1>2. Тогда ввиду только что доказанный теоремы Un делиться на Un1 причем 1<Un1<Un, а это и означает, что Un – составное число.
Существует огромное количество различных обобщений чисел Фибоначчи. Одним из наиболее интересных является гипотенузный ряд Шишкова.
Существует связь между теоремой Пифагора и числами Фибоначчи.
С2+B2=A2 – теорема Пифагора.
Поместим для наглядности рядом числа Фибоначчи:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4161 6765...
Полагая, что числа Фибоначчи непосредственно связаны с прямоугольными треугольниками, берем попарно суммы, состоящие из квадратов чисел Фибоначчи, и находим в этом же ряду соответствующее число, равное квадрату гипотенузы, или сумме двух возведенных в квадрат чисел Фибоначчи. Эти числа, равные квадрату гипотенузы, сумме двух возведенных в квадрат катетов, подчеркнуты в ряду Фибоначчи чертой. Эти подчеркнутые числа Ф являются и квадратом гипотенузы ранее расположенных катетов, и, одновременно, катетами, квадрат гипотенузы которых расположен дальше в ряду Фибоначчи.