88918

Задачи, связанные с последовательностью Фибоначчи

Реферат

Математика и математический анализ

Данная исследовательская работа посвящена рассмотрению некоторых числовых последовательностей, заданных рекуррентно, их свойств и задач с ними связанных. Этого материала нет в школьной программе, при изучении числовых последовательностей мы сталкиваемся с рекуррентным заданием лишь на примере...

Русский

2015-05-06

2.03 MB

11 чел.

                                                          Содержание

Введение

3

1.  Последовательность Фибоначчи

  4 - 8

2.  Свойства последовательности Фибоначчи

 9 - 12

3. Последовательность Фибоначчи и золотое сечение

    13

4. Задачи, связанные с последовательностью Фибоначчи

14 - 18

5. Числа Каталана

 19 -25

Заключение

    26

Список литературы и других источников

    27

ВВЕДЕНИЕ

Данная исследовательская работа посвящена рассмотрению некоторых числовых последовательностей, заданных рекуррентно, их свойств и задач с ними связанных.  Этого материала нет в школьной программе,  при изучении числовых последовательностей мы сталкиваемся с рекуррентным заданием лишь на примере арифметической и геометрической прогрессий, но изучение таких последовательностей – достаточно увлекательный процесс.

Теория по данному вопросу достаточно простая, лаконичная, пронизывающая все разделы математики, применимая как в геометрии, так и в математическом анализе. Задачи, рассмотренные в этой работе, принадлежат крупнейшим математикам. Основы этой теории были впервые опубликованы в середине восемнадцатого века.  В последние годы изменился кругозор читателей математической литературы, и многие достижения в теории чисел, упоминаемые в популярной литературе, не подкреплены знаниями читателей. Поэтому хотелось бы рассмотреть  одни из самых известных последовательностей, заданных рекуррентным способом,  изучить их свойства и значимость в истории развития математики.

                                        §1.  Последовательность Фибоначчи

       Древняя история богата выдающимися  математиками. Многие достижения древней математической науки до сих пор вызывают восхищение остротой ума

их авторов, а имена Евклида, Архимеда, Герона  известны каждому образованному человеку. Иначе обстоит дело с математикой средневековья. Кроме Франсуа Виета, жившего, впрочем, уже в шестнадцатом столетии, и математиков более близких нам времен, школьный курс математики не называет ни одного имени, относящегося к средним векам. Это, конечно, не случайно. Математика в эту эпоху развивалась

чрезвычайно медленно, и крупных математиков тогда было очень мало.

Тем больший интерес представляет для нас  сочинение «Liber abacci» («Книга об абаке»), написанная знаменитым итальянским математиком Леонардо из Пизы, который известен больше по своему прозвищу Фибоначчи (Fibonacci-—сокращенное filius Bonacci, т. е. сын Боначчи). Эта книга, написанная в 1202 г.,

дошла до нас во втором своем варианте, который относится к 1228 г.

«Liber abacci» представляет собой объемистый труд, содержащий почти все арифметические и  алгебраические сведения того времени и сыгравший  заметную роль в развитии математики в Западной Европе в течение нескольких следующих столетий. В частности, именно по этой книге европейцы познакомились с индусскими («арабскими») цифрами. Сообщаемый в «Liber abacci» материал поясняется на большом числе задач, составляющих значительную часть этого трактата.

Среди многих задач он привёл следующую:

«Пара кроликов приносит раз в месяц приплод из двух крольчат (самца и самки), причём молодые крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов?»

Из условия задачи следует, что через месяц будет две пары кроликов. Через месяц приплод даст только первая пара кроликов, и получится три пары. А ещё через месяц приплод дадут и исходная пара кроликов, и пара кроликов. Появившихся два месяца тому назад. Поэтому всего будет пять пар кроликов.

Перейдем теперь от кроликов к числам рассмотрим следующую числовую последовательность:

F(n):   1; 2; 3; 5; 8; 13; 21; 34; …

в которой каждый член равен сумме двух предыдущих членов, т. е. при всяком

n  > 2

   F(n) = F(n – 1) + F(n – 2)     или        an = an—1 + an – 2     (1)

Такие последовательности, в которых каждый член определяется как некоторая функция предыдущих (причём равенство (1) может содержать некоторые коэффициенты перед  an—1  и  an – 2 ), часто встречаются в математике и называются  рекуррентными или, по-русски, возвратными  последовательностями.

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

последовательности цифр десятичного разложения рационального числа (и вообще любые периодические последовательности), последовательности коэффициентов частного от деления двух многочленов, расположенных по возрастающим степеням х, и т. д. Отсюда видно, что с возвратными   последовательностями в курсе математики средней школы приходится встречаться весьма часто. Теория возвратных последовательностей составляет особую главу математической дисциплины, называемой исчислением конечных разностей. Основы теории возвратных последовательностей были разработаны и опубликованы в двадцатых годах восемнадцатого века французским математиком Муавром и одним из первых по времени членов Петербургской Академии наук швейцарским математиком Даниилом Бернулли. Развёрнутую теорию дал крупнейший математик восемнадцатого века петербургский академик Леонард Эйлер, посвятивший возвратным последовательностям  тринадцатую главу своего «Введения в анализ бесконечно-малых».

Количество слагаемых в правой части равенства (1) определяет порядок возвратной последовательности. Само равенство (1) называют уравнением возвратной последовательности.

Заметим, что по одному только рекуррентному условию нельзя вычислить члены последовательности, т. к. по такому условию можно составить бесконечно много последовательностей. Для однозначного построения последовательности необходимо  задать дополнительные условия – несколько первых членов.

У последовательности Фибоначчи начальными членами являются две единицы.

До сих пор мы определяли число Фибоначчи рекуррентно, т. е. индуктивно, по их номеру. Оказывается число этой последовательности можно определить и непосредственно, аналитически – как некоторую функцию номера.

Исследуем для этого различные последовательности, удовлетворяющие соотношению (1).

Все такие последовательности будем называть решениями уравнения (1).

Будем обозначать буквами V, V/ и V// соответственно последовательности

 v1,   v2 ,   v3 , …

 v1/ ,  v2/ ,  v3/ , …

v1// ,  v2// ,  v3// , …

Есть две простые леммы:

1)Если V есть решение уравнения (1), и   с -  произвольное число, то последовательность  cV   есть также решение данного уравнения.

2) Если последовательности V и V" являются решениями уравнения (1), то и их сумма также является решением данного уравнения.

Пусть теперь V/ и  V// два непропорциональных решения уравнения (1), т. е. такие, что при любом постоянном С найдётся такой номер n, что     

Покажем, что всякую последовательность V можно представить в виде:

C1V/ + C2V// (2), где C1 и C2 -  некоторые постоянные.

Т. к. последовательности   V/   и V//  непропорциональны, то  непропорциональны и её соответствующие члены (это утверждение можно доказать методом от противного, применив индукцию).

Теперь найдём последовательность V, она будет определена, если заданы её два начальных члена.

Чтобы  V = C1V/ + C2V// , найдём такие с1 и с2, чтобы имела место система:

 c1v1/ +c2v1// = v1,

 c1v2/ + c2v2// = v2.

Тогда на основании двух лемм, указанных ранее,  C1V/ + C2V//  даст нам последовательность V.

В силу непропорциональности последовательностей, эта система будет разрешима  относительно  c1   и  c2, каковы бы ни были при этом числа v1 ,  v2.       

Знаменатель этих дробей не может быть равен нулю. а подставив полученные значения в  C1V/ + C2V// мы и получим  требуемое представление последовательности  V.

Для получения всех решений уравнения  V = C1V/ + C2V// , нам достаточно найти два его какие-нибудь непропорциональные решения.

Будем искать эти решения среди геометрических прогрессий. В соответствии с леммой №1, мы имеем право выбрать только такие прогрессии, первый член которых равен 1.

Итак. возьмём прогрессию:  1; q ; q2 ; …

Чтобы она являлась решением уравнения  V = C1V/ + C2V// , необходимо. чтобы для любого n  выполнялось  qn – 2 + qn – 1 = qn   или  1 + q = q2 .

Корни этого квадратного уравнения    и   .

с1 + с2 = 1    и

с1 + с2 =1

Решив эту систему, получим:

с1 =   ,   с2 = ,

откуда   V = .

Эта формула называется формулой Бине (по имени получившего её математика).

Полученная формула и есть аналитическое задание последовательности Фибоначчи  F(n).

§2.  Свойства последовательности Фибоначчи

     Последовательность Фибоначчи обладает рядом свойств.

Выведем выражение этих чисел через  . Для этого установим связь между числами данной последовательности и следующей комбинаторной задачей.

«Найти число n – последовательностей, состоящих из нулей и единиц, в которых никакие две единицы не идут подряд».

Чтобы установить эту связь  вспомним задачу о кроликах,  с которой мы начали наше знакомство с последовательностью чисел Фибоначчи; сопоставим последовательности, о которой идёт  речь в условии,  пару кроликов по правилу: единицам соответствуют месяцы появления на свет одной из пар «предков» данной пары (включая  и исходную), а нулями – все остальные месяцы. Например, последовательность 010010100010 устанавливает такую «генеалогию» - сама пара появилась в конце 11-го месяца, а её родители – в конце 7-го, «дед» - в конце 5-го, а «прадед» - в конце второго. Исходная пара кроликов зашифровывается при этом последовательностью  000000000000.

Ясно, что при этом ни в одной последовательности не могут стоять две единицы подряд – только что появившаяся пара не может, по условию, принести приплод в следующем месяце. Кроме того, при указанном правиле различным последовательностям отвечают различные пары кроликов, и обратно, две различные пары кроликов имеют разную «генеалогию», так как, каждый раз пара кроликов даёт приплод, состоящий также из одной пары.

Установленная связь показывает, что число n –последовательностей, обладающих указанным свойством, равно F(n).

Докажем теперь, что

F(n) = + ++ …+ , где   , если  n  нечётно,  и    , если  n  чётно, иными словами  .

Есть такая комбинаторная задача о лестнице: «Сколькими способами можно расставить n нулей и k единиц так,  чтобы никакие две единицы не стояли рядом». Решение этой задачи можно изобразить в виде лестницы, причём нуль означает место, где ломаная идёт вправо, а единица – место, где она идёт вверх (как показано на рисунке). При этом, так как ступенек двойной высоты на лестнице нет, в последовательности не могут идти две единицы подряд. Таким образом, число последовательностей из n нулей и k единиц будет равно числу лестниц, т. е.   . Число же таких последовательностей, в которые входит ровно k единиц и   nk   нулей, равно  . Так как при этом должно выполнятся неравенство      knk +1,  то k изменяется от 0 до  . Применяя правило суммы, приходим к соотношению  F(n) = + ++ …+ .

Данное равенство можно доказать иначе: по свойству сочетаний                        =  +. Легко заметить, что последовательность чисел Фибоначчи обладает схожим свойством:      F(n) = F(n – 1) + F(n – 2).

Процесс последовательных разбиений.

Заметим, что для решения комбинаторных задач часто применяют такой метод – устанавливают для задачи рекуррентное соотношение и показывают, что оно совпадает с рекуррентным соотношением для другой задачи, решение которой нам уже известно. Если при этом совпадают и начальные члены последовательностей в достаточном числе, то обе задачи имеют одинаковые решения.   

Перечислим ещё свойства, которыми обладают числа последовательности Фибоначчи:

  1.  Число Фибоначчи    есть ближайшее целое число к    , т. е. к   n-му  члену геометрической прогрессии (, первый член которой   , а знаменатель равен а.  (это свойство доказывается с помощью записи формулы Бине  и установления того факта, что абсолютная величина разности между членом последовательности Фибоначчи и членом данной прогрессии меньше   .

Если использовать теорию пределов, то  легко

можно показать, несколько видоизменив доказательство этой

теоремы,  что

= 0.

Пользуясь доказанной теоремой, можно вычислять

числа Фибоначчи при помощи таблиц логарифмов.  

Вычислим например вычислим  .

       

a =   = 1,6180      

 = 14∙ -  = 2,5762

 = 376,9

Ближайшее целое число к 376, 9 является число 377, это и есть  .

При вычислении чисел Фибоначчи с большими

номерами мы уже не сможем по таблицам

логарифмов определить все цифры числа, а сможем указать

только несколько первых цифр его, так что

вычисление окажется приближенным.

  1.  Свойства чисел Фибоначчи, связанные с делимостью:
  2.  Соседние числа Фибоначчи взаимно просты.
  3.  Число Фибоначчи четно тогда и только тогда, когда его номер делится на 3.
  4.  Число Фибоначчи делится на 3 тогда и только тогда, когда его номер делится на 4.
  5.  Число Фибоначчи делится на 4 тогда и только тогда, когда его номер делится на 6.
  6.  Число Фибоначчи делится на 5 тогда и только тогда, когда его номер делится на 5.
  7.  Число Фибоначчи делится на 7 тогда и только тогда, когда его номер делится на 8.
  8.  Число Фибоначчи делится на 16 тогда и только тогда, когда его номер делится на 12.

(Эти свойства можно доказать, используя свойства делимости чисел, алгоритм Евклида , индукцию, а также свойство биномиальных коэффициентов: «если р – простое, а k≠0  и  kp, то   делится на р»).

  1.  Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.
  2.  Производящей функцией последовательности чисел Фибоначчи является:

  1.   Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются числами Фибоначчи.

§3.  Последовательность Фибоначчи и золотое сечение

      Самым известным свойством последовательности является: отношение следующего и предыдущего членов является подходящим числом золотой пропорции.

«Золотое сечение»  (золотая пропорция, деление в крайнем и среднем отношении) — деление непрерывной величины на две части в таком отношении, при котором меньшая часть так относится к большей, как большая ко всей величине.

Отношение большей части к меньшей в этой пропорции выражается квадратичной иррациональностью.

Если рассмотреть золотой прямоугольник, смежные стороны которого находятся в золотом соотношении, можно убедиться, что его можно построить,  опираясь на последовательные члены последовательности Фибоначчи: вначале соединяются два квадрата со стороной 1, затем к ним присоединяется квадрат со стороной 2 и т. д. присоединяются квадраты, стороны которых соответствуют числам Фибоначчи как показано на рисунке.

§4.  Задачи, связанные с последовательностью Фибоначчи

1. Числа Фибоначчи появляются в вопросах, связанных с исследованием путей в различных геометрических конфигурациях. Рассмотрим сеть путей, изображённую на рисунке (такую сеть в математике принято называть ориентированным графом), и подсчитаем число путей, которыми можно, двигаясь вдоль стрелок, перейти из вершины А или вершины В  в вершину .

                      

Обозначим числа таких путей     . Ясно, что при начале движения, как из точки А, так и из точки В, в вершину  можно попасть двумя способами: через вершину  с последующим шагом вдоль наклонного ребра  и через вершину   с последующими шагом вдоль горизонтального ребра.

Значит  an = an—1 + an – 2 ,      bn = bn—1 + bn – 2 .

Остаётся заметить, что  a1 = 1 = a2  и  b1 = 1 = b2  , т. е. количество путей соответствует числам Фибоначчи. Также встречаются задачи не на подсчёт путей, а на выбор рационального перехода по путям – это различные игровые задачи, в которых числа Фибоначчи либо играют роль координат узловых точек ориентированного графа, либо помогают выстроить последовательность.

2. Задача

«Имеется 76 карточек, на которых написаны разные числа. Эти карточки разложены на столе по кругу числом вниз. Надо найти какие-нибудь три идущие подряд карточки такие, что число, написанное на средней из этих трёх карточек, больше, чем на двух соседних. Перевернут можно последовательно не более 10 карточек. Как надо действовать, чтобы наверняка найти три карточки, для которых выполняется указанное условие?»

Решение:

Для построения рассуждений нам потребуется последовательность Фибоначчи:

1; 1; 2; 3; 5; 8; 13; 21; …

an = an—1 + an – 2 ,   а1 = а2 = 1.

Число карточек  76 = 21 + 21 + 34. (т. е. можно будет использовать данную закономерность)

Пусть  N  карточек расположены по кругу в вершинах  N – угольника.

Если  a, b – карточки, то  (a; b) – «a лежит раньше b  по часовой стрелке».

Дуга  (a; b) – промежуток между a  и  b.

Длина  дуги  (a; b) – число сторон  N – угольника  между  a  и  b.

Назовём тройкой  ранга  k  три открытые (числом вверх) карточки  (a; b; c), удовлетворяющие условиям:

  1.  на дугах  (a; b)  и  (b; с)  нет открытых карточек;
  2.  длины дуг (a; b)  и  (b; с)  либо обе равны xk, либо одна - xk, а вторая –

   xk+1;

  1.  число на карточке  b  больше числа на карточке  а и  с.

В нашей задаче надо найти тройку ранга 1.

Посмотрим, как из тройки ранга  k  получить тройку ранга 1.

Пусть тройка  (a; b; c) – тройка ранга  k .

1 случай: длина обеих дуг (a; b)  и  (b; с)  равны  xk.

На дуге  (a; b)  откроем точку  d  так, что длины дуг  (a; d)  и  (d; b)  равны  xk-2  и

xk-1 соответственно. При этом возможны два варианта:

         а) d < b  (d; b; c) – тройка ранга  k – 1;

         б) d > b  (a; d; b) – тройка ранга k – 2.

2 случай: Длина  дуги   (a; b)  - xk+1  (для определённости), а дуги  (b; с) -   xk.

На большей дуге откроем точку d так, что длины дуг (a; d) и (d; b) равны  xk  xk-1.

Возможны два варианта:

         а) d < b  (d; b; c) – тройка ранга  k – 1;

         б) d > b  (a; d; b) – тройка ранга k – 1.

Применяя последовательно (в обоих случаях) этот способ мы получим тройку

ранга 1, открыв при этом не более k – 1 карточки.

Остаётся для решения найти какую-нибудь тройку ранга  k.

В нашем случае:  N = 76 = 21 + 21 + 34 = 2 xk + xk+1.

И всего (с начальными a;  b  и  с  нам предстоит открыть  k + 2 числа, т. е. в

нашем случае – 10 чисел).

Ответ: для нахождения данной тройки чисел достаточно открыть 10 карточек.

3.  Задача – шутка

«Докажем», что 64 = 65».

Возьмём для этого квадрат со стороной 8 и разрежем его на части, как показано на рисунке.

       

Эти части мы сложим в прямоугольник со сторонами 13 и 5, т. е. с площадью, равной 65.

 

Объяснение этому, на первый взгляд загадочному, явлению найти нетрудно. Всё дело в том, что точки A, B, C и D на самом деле не лежат на одной прямой, а являются вершинами параллелограмма, площадь которого  как раз и равна «лишней» единице.

Это правдоподобное, но неверное «доказательство» заведомо ложного высказывания (такие «доказательства» ещё называют «софизмами»), можно проделать ещё более наглядно и «убедительно», если взять вместо квадрата со стороной 8 квадрат со стороной, равной некоторому числу Фибоначчи с достаточно большим номером, an.  Разобьём этот квадрат на части (см. рисунок) и сложим из этих частей прямоугольник. «Пустота» в виде параллелограмма, вытянутого вдоль диагонали прямоугольника, имеет площадь, равную единице. Наибольшая ширина этой щели, т. е. высота параллелограмма, равна, как легко вычислить,

.

Поэтому, если мы возьмём квадрат со стороной 21 см и «превратим» его в прямоугольник со сторонами 34 и 13 см, то наибольшая ширина щели получится

0,4 мм, что почти незаметно для глаза.

§5.  Числа Каталана

При решении многих задач часто приходится сталкиваться с последовательностями, заданными рекуррентно, но, в отличии от последовательности Фибоначчи, не всегда возможно получить её аналитическое задание.

В 1973 году в США был  издан «Справочник числовой последовательности» А. Слоуна.  В нём описано более 2300 целочисленных числовых последовательностей, каждая из которых имеет свой номер.

Рассмотрим числовую последовательность:

1; 2; 5; 14; 42; 132; 429; …, имеющую в справочнике номер 577.

Члены этой последовательности названы числами Каталана. Они не так хорошо известны, как числа Фибоначчи, но имеют особенность также появляться в различных задачах, особенно в комбинаторных. В 1971 году математик Генри Гулд опубликовал библиографию на применение чисел Каталана в 243 случаях. Во многих из них известнейшие математики и не подозревали, что имеют дело с этими числами.

Первым с числами Каталана столкнулся Леонард Эйлер. Он подсчитал, сколькими способами выпуклый многоугольник может быть разделён на треугольники непересекающимися диагоналями.

В качестве примера можно привести способы разбиения на треугольники следующих фигур: квадрата, пятиугольника и шестиугольника.

Заметим, что в каждом из случаев¸ независимо от количества сторон                     n- угольника, число диагоналей равно (n – 3),  а число треугольников (n – 2).

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

             

                                                  

                                                                         

         1                              2                                    5                                          14               

и  т. д.

     Эйлер, используя метод математической индукции, который, по его словам, здесь оказался трудоёмким, получил такую формулу:

Очень простые рекуррентные формулы получаются, если поместить в начале последовательности ещё одну единицу.

Пусть k – последнее вычисленное число Каталана, а  n –  номер следующего числа.

Тогда это число вычисляется по формуле: .

Современник Эйлера, Иоганн Андрес фон Сегнер, получил загадочную рекуррентную формулу для последовательности Каталана вида: 1; 1; 2; 5; …

Запишем в ряд все уже найденные числа Каталана, а под ними запишем те же числа в обратном порядке. Умножим каждое верхнее число на соответствующее нижнее и сложим получившиеся произведения; результат и будет следующим числом Каталана.

1    1   2   5   14

*

14  5   2   1   1

14 + 5 + 4 +5 +14 = 42

Теперь вернёмся к задаче о разбиении многоугольников. Эта задача изоморфна  и задачам, казалось бы с ней. Эта задача изоморфна  и задачам, казалось бы с ней не связанным.

Сам Ижен Шарль Каталан, бельгийский математик, в 1838 г. решил следующую задачу: «Пусть имеется цепочка из  n  букв, расположенных в заданном порядке. Необходимо расставить  (n – 1) пару скобок так, чтобы внутри каждой пары стояло ровно два «выражения». Этими спаренными выражениями могут быть либо две соседние буквы, либо два соседних выражения. Сколькими способами могут быть поставлены скобки?»

Для букв  a и b имеется только одна возможность: (ab).

Для трёх букв таких возможностей  две: ((ab) c) (a (bc)).

Для четырёх букв количество способов  увеличится до пяти:

((ab)(cd))  (((ab) c) d)   (a (bc) d)  ((a (bc) d).

Эти числа  1; 2; 5 – первые числа Каталана, оказывается, числа Каталана дают нам количество способов расстановки скобок в буквенных цепочках соответствующих длин.

В 1961 г. Фордер, описывая числа Каталана, указал простой способ взятого однозначного соответствия между подсчётом комбинаций в многоугольниках и расстановкой скобок в буквенных цепочках.

Рассмотрим, например, семиугольник:

Обозначение основания идёт последним и обозначение для него однозначно определяется триангуляцией («триангуляция» - разбиение  на треугольники). Если применить указанный приём для выше перечисленных многоугольников, то получим цепочки букв с расставленными скобками.

Английский математик Артур Кэли доказал, что числа Каталана перечисляют все плоские  корневые кубические деревья (именно, n – е число Каталана равно количеству плоских корневых кубических деревьев с (n + 1) - ой концевой вершиной).

Дерево – это связный граф (вершины, соединённые отрезками), не имеющий циклов.

«Плоский» означает, что граф нарисован на плоскости без пересечений.

«Корневое» - это дерево имеет ствол, конец которого имеет корень.

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

«Кубическое» означает, что в каждой вершине (кроме корня и концов веток) дерево разветвляется, образуя точки, в которых встречаются три ребра.

Под каждой цепочкой букв со скобками записано двоичное число, получаемое заменой всех скобок «1», а всех букв – «0», пропуская правые скобки. Для правых скобок нет необходимости вводить обозначение, т. к. заданное положение левых скобок и метод группировки букв определяет постановку скобок единственным образом.

Рассмотрим ещё такую задачу:

«Возьмём шахматные доски со сторонами 2; 3; 4; …, в которых закрашены все квадраты северо-западнее главной диагонали. Требуется провести ладью из левого нижнего угла в правый верхний. Двигаться можно, не заходя при этом на закрашенные клетки. Сколько существует путей ладьи на доске со стороной а

Решение:

     

  

 

Под стороной длины n напишем двоичное число, соответствующее корневому дереву (кубическому) с  n концевыми вершинами.

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

 

 

Заключение

В  работе  на примере двух наиболее широко известных возвратных последовательностей были рассмотрены способы задания рекуррентных последовательностей, их некоторые свойства, применение в различных разделах математики.

Все поставленные в данном исследовании цели были достигнуты: сделан исторический экскурс по теории вопроса, рассмотрены различные формулы и их выводы, показано применение изучаемых в работе объектов на примере различных задач. Все рассмотренные задачи  сопровождаются подробными пояснениями, доказательствами и иллюстрациями.

При работе над данной темой были использованы разнообразные источники информации такие как: печатные и электронные издания, энциклопедическая и учебная литература.

     Выбранная тема зачастую остаётся за страницами школьного учебника, хотя она очень интересна и многогранна.  В работе показана связь таких разделов математики как: математический анализ и геометрия, комбинаторика и теория чисел.

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

Список литературы

1.  Виленкин Н. Я. Комбинаторика. М.: Наука, 1969

2.  ПОПУЛЯРНЫЕ ЛЕКЦИИ ПО МАТЕМАТИКЕ. М.: Наука, 1978

  1.        выпуск 1.   А. И. М а р к у ш е в и ч. Возвратные последовательности.
  2.        выпуск  6.   Н. Н. Воробьев. Числа Фибоначчи.
  3.        выпуск  21.  Л. И. Головин, И. М. Яглом. Индукция в геометрии.
  4.        выпуск 11.   Я. С. Дубнов. Ошибки в геометрических доказательствах.
  5.        выпуск 32 .  Е. С. В е н т ц е л ь. Элементы теории игр.

Электронные источники:

http://ru.wikipedia.org/wiki/Числа_Фибоначчи

www.math.ru

www.sciteclibrary.ru

 


 

А также другие работы, которые могут Вас заинтересовать

42278. СКЛЕИВАНИЕ ЛИНЗ 408.5 KB
  Если например между положительной линзой из стекла марки К8 и отрицательной линзой из стекла марки ТФ1 будет воздушный промежуток то количество света отражаемого свободными поверхностями составит 18. Приведя поверхности в соприкосновение или заполнив промежуток между ними средой с показателем преломления равным или близким показателю преломления одной из линз потери света на отражение уменьшаются примерно до 10. Линзы в большинстве случаев склеивают веществами бальзамин М ОК72Ф ОК50 и др.
42279. Настройка статических маршрутов 58.5 KB
  Щелкните ПК офиса филиала BOpc и перейдите по ссылкам Desktop Commnd Prompt . Запишите IPадрес ПК офиса филиала BOpc и адрес шлюза по умолчанию. Адрес шлюза по умолчанию – это IPадрес интерфейса FstEthernet для Офиса филиала BrnchOffice.1 адрес шлюза по умолчанию для локальной сети Офиса филиала BrnchOffice в запросе команды в ПК офиса филиала BOpc.
42280. Исследование индуктивно-связанных цепей 288.5 KB
  Целью работы является экспериментальное определение параметров двух индуктивно связанных катушек и проверка основных соотношений индуктивно связанных цепей при различных соединениях катушек. Подготовка к работе Схема замещения двух индуктивно связанных катушек удовлетворительно учитывающая электромагнитные процессы в диапазоне низких и средних частот представлена на рис. 1 где L1 R1 и L2 R2 индуктивности и сопротивления соответственно первой и второй...
42281. ЗАКОНЫ СТОЛКНОВЕНИЙ 931 KB
  Обозначим массы шаров и скорости шаров до удара и а скорости после удара и рис. 5 Скорости шаров после удара получим умножив 5 на и вычтя результат из 3 а затем умножив 5 на и сложив результат с 3: . Рассмотрим неупругое столкновение двух шаров массами и скорости которых до удара и . Установка предназначена для измерения скорости двух подвижных...
42282. ОСНОВНОЕ УРАВНЕНИЕ ДИНАМИКИ ВРАЩАТЕЛЬНОГО ДВИЖЕНИЯ ВОКРУГ НЕПОДВИЖНОЙ ОСИ 981 KB
  Изучение динамики вращательного движения твердого тела. Исследование зависимости угла поворота твердого тела от времени, экспериментальная проверка основного уравнения динамики вращательного движения, определение момента инерции твердого тела как коэффициента пропорциональности в основном уравнении
42283. ИЗУЧЕНИЕ УПРУГИХ СВОЙСТВ ПРУЖИНЫ 2.68 MB
  Если пружина находится в равновесии то силы действующие на любую часть пружины уравновешены рис. По закону Гука сила упругости пропорциональна деформации пружины : 1 где проекция силы упругости на ось направленную вдоль оси пружины рис. Рис. Одной из упругих характеристик...
42284. ЦЕНТРОБЕЖНАЯ СИЛА 843 KB
  Исследование зависимости величины центробежной силы от массы тела угловой скорости и расстояния до оси вращения. Вместе с платформой вращается привязанная к оси вращения небольшая тележка. Рассмотрим небольшой груз массы m подобно тележке привязанный к оси вращения нерастяжимой невесомой нитью и вращающийся вместе с платформой.1 этот груз схематически изображён слева от оси вращения.
42285. ИЗУЧЕНИЕ КОЛЕБАНИЙ СВЯЗАННЫХ МАЯТНИКОВ 1.67 MB
  Измерение собственных частот колебаний и частоты биений экспериментальная проверка соотношения между этими частотами. Теоретическая часть Биения Гармоническими колебаниями называются колебания которые описываются формулой 1 где координата колеблющейся точки амплитуда колебаний циклическая частота период колебаний начальная фаза. Амплитуда колебаний и начальная фаза определяются начальными условиями:...
42286. ОПРЕДЕЛЕНИЕ МОМЕНТА ИНЕРЦИИ ТВЕРДОГО ТЕЛА И ПРОВЕРКА ТЕОРЕМЫ ШТЕЙНЕРА 1.78 MB
  Теоретическая часть Момент инерции это величина зависящая от распределения масс в теле и являющаяся мерой инертности тела при вращательном движении. Момент инерции тела относительно оси вращения определяется выражением 1 где элементарные точечные массы на...