https://doi.org/10.53656/math2024-3-7-dou

2024/3, стр. 336 - 350

ДВУКРАТНО БРОЕНЕ И ЧИСЛА НА ФИБОНАЧИ

Резюме: Предложен е комбинаторният принцип за двукратно броене при доказване на комбинаторни тъждества, включващи числата на Фибоначи. Той се прилага лесно от учениците и им позволява запомняне с лекота на самите тъждества, творческо приложение в нови ситуации, (пре)откриване на резултати и задаване на съдържателни въпроси. Методът е ориентиран основно към подготовката на ученици, участващи в математически състезания.

Ключови думи: комбинаторни тъждества; двукратно броене; редица на Фибоначи; състезания по математика

1. Увод

Споменатият в резюмето метод за двукратно броене е показан в решенията на конкретни задачи. Списъкът на илюстриращите тук тъждества може да се продължи и от самите ученици, за което е добре да бъдат насърчени, тъй като фантазията им понякога има добри попадения.

Не се налага да се познава методът на математическата индукция. За последните задачи е необходимо да се знае формулата за броя на комбинациите без повторения \(\binom{n}{k}\) за \(0 \leq k \leq n\) и \(\binom{n}{k}=0\) за всички останали \(k, n\). Тази формула обикновено е известна на учениците от 5 клас в математически гимназии и паралелки в България. Все пак част от задачите поради трудността си са по-подходящи за школите в 7 и дори в 8 клас. В някои задачи е използвано означението за цяла част \(\lfloor\).\(\rfloor .\)

Познаването на означението за сума (с което някои от тези ученици са запознати, а други – не, но могат да го схванат сравнително бързо, ако е илюстрирано с примери) позволява по-кратки означения, но при първоначалното запознаване с метода и при ученици без достатъчен опит с него е добре за яснота да бъде записано (и) в разгънат вид. Всички променливи в изложението представят естествени числа (освен ако условието изрично допуска стойността да е и 0), като това няма да бъде указвано нататък. С оглед на удобството класическата дефиниция за числата на

Фибоначи (вж. напр. Hoggatt 1969) е изведена като следствие на избраната тук.

Дефиниция. Нека \(f_{n}\) е броят на начините да се изкачим до \((n-1)\)-то стъпало на стълбище с произволен брой стъпала, ако на всяка стъпка можем да изкачваме по едно или две стъпала. Очевидно \(f_{1}=f_{2}=1\).

За пълнота нека дефинираме \(f_{0}=0\). До (\(n-1\) )-ото стъпало, при \(n \geq 3\), можем да се изкачим само от \((n-2)\)-то или от \((n-3)\)-то, така че \(f_{n}=f_{n-1}+f_{n-2}\). Тези равенства задават редицата на Фибоначи (0,) 1, \(1,2,3,5,8,13,21,34, \ldots\)

Забележка. Връзката между рекурентната дефиниция и „изкачването на стълби“ е добре известна и често е сред фактите, с които учениците се запознават при първите си срещи с числата на Фибоначи (разбира се, при класическата рекурентна дефиниция това свойство се доказва, виж например (Alfutova & Ustinov 2002)). Това, което ще се постараем да по-кажем в тази статия, е как можем да го използваме за доказване на широк клас от тъждества за числа на Фибоначи, част от които са известни (Koshy 2001; Debnath 2011; Kortezov 2019), а други поне засега не откриваме в литературата.

2. Комбинаторни принципи

Дефиниция. Разбиване на крайното множество A e такава фамилия

A1, A2, . . . , Ak от негови дизюнктни непразни подмножества, че (за учениците, които се срещат за пръв път с понятието „дизюнктни“ то означава, че никои две от тях нямат общ елемент).

Принцип на събирането (на разбиването). Нека A1 , A2, . . . , Ak е разбиване на крайното множество A. Тогава

|A| = |A1| + |A2| + · · · + |Ak|.

(|X| e броят на елементите на множеството X.)

Принцип на умножението (на декартовото произведение). Декартово произведение на множествата A и B е множеството

A × B = {(a, b) | a ∈ A, b ∈ B}.

Ако A и B са крайни множества, то A × B също е крайно и броят на елементите му е |A × B| = |A|.|B|.

Принцип на двукратното броене. Броят на елементи на дадено множество не зависи от начина на преброяването им.

3. Примери

Задача 1. Докажете, че \(f_{2 n+1}=f_{n}^{2}+f_{n+1}^{2}\).

Решение. Има \(f_{2 n+1}\) начина да се изкачи стълбище с \(2 n\) стъпала по едно или по две на крачка. Да разбием тези начини на две непресичащи се подмножества.

• Ако се стъпва на \(n\)-тото стъпало, тогава за всяка половина на стълбището има по \(f_{n+1}\) начина. От комбинаторния принцип за умножението (комбинирайки всеки от първите с всеки от вторите) имаме общо \(f_{n+1}^{2}\) начина.

• Ако се прескача \(n\)-тото стъпало, тогава за достигане на (\(n-1\) )-то стъпало има \(f_{n}\) начина, след това се стъпва на (\(n+1\) )-то стъпало и за останалите \(n-1\) стъпала докрая има пак \(f_{n}\) начина. Или от принципа за умножението – общо \(f_{n}^{2}\) начина.

Затова, от комбинаторния принцип за събирането, всички начини за изкачване на \(2 n\) стъпала са \(f_{2 n+1}=f_{n+1}^{2}+f_{n}^{2}\).

Задача 2. Докажете, че \(f_{2 n}=f_{n}\left(f_{n-1}+f_{n+1}\right)\).

Решение. Има \(f_{2 n}\) начина да се изкачи стълбище с \(2 n-1\) стъпала по едно или по две на крачка. Да разбием тези начини на две непресичащи се подмножества.

• Ако се стъпва на \(n\)-тото стъпало, за долната половина на стълбището има \(f_{n+1}\) начина, а за горната има \(f_{n}\) начина. Или общо \(f_{n+1} \cdot f_{n}\) начина.

• Ако се прескача \(n\)-тото стъпало, за долната половина на стълбището има \(f_{n}\) начина, а за горната \(-f_{n-1}\) начина. Или общо \(f_{n} \cdot f_{n-1}\) начина.

Така всички начини са \(f_{2 n}=f_{n}\left(f_{n-1}+f_{n+1}\right)\).

Задача 3. Докажете, че \(f_{n+m+1}=f_{n} f_{m}+f_{n+1} f_{m+1}\).

Решение. Има \(f_{n+m+1}\) начина да се изкачи стълбище с \(n+m\) стъпала по едно или две на крачка. Да ги разбием отново на две подмножества.

• Ако се стъпва на \(n\)-тото стъпало, то за долната част на стълбището има \(f_{n+1}\) начина, а за горната има \(f_{m+1}\) начина.

• Ако се прескача \(n\)-тото стъпало, то за долната част на стълбището има \(f_{n}\) начина, а за горната има \(f_{m}\) начина.

Така всички начини са \(f_{n+1} \cdot f_{m+1}+f_{n} \cdot f_{m}\). □

Задача 4. Докажете, че \(f_{3 n+1}=f_{n+1}^{3}+f_{n}^{2}\left(2 f_{n+1}+f_{n-1}\right)\).

Решение. Първи метод: Има \(f_{3 n+1}\) начина да се изкачи стълбище с \(3 n\) стъпала по едно или по две на крачка. Сега всички начини можем да разбием на четири непресичащи се множества.

• Ако се стъпва на \(n\)-тото и на \(2 n\)-тото стъпало, за всяка третина на стълбището има \(f_{n+1}\) начина.

• Ако се прескача \(n\)-тото стъпало, но се стъпва на \(2 n\)-тото:

◦ от земята до (\(n-1\) )-то стъпало (\(n-1\) стъпала) има \(f_{n}\) начина;

◦ от (\(n+1\) )-то до \(2 n\)-тото стъпало (\(n-1\) стъпала) има \(f_{n}\) начина;

◦ от \(2 n\)-тото до \(3 n\)-тото стъпало (\(n\) стъпала) има \(f_{n+1}\) начина.

• Сходна е ситуацията и ако се прескача \(2 n\)-тото стъпало, но се стъпва на \(n\)-тото.

• Ако се прескача и \(n\)-тото, и \(2 n\)-тото стъпало:,

◦ от земята до (\(n-1\) )-то стъпало (\(n-1\) стъпала) има \(f_{n}\) начина;

◦ от \((n+1)\)-то до \((2 n-1)\)-то \(\left(n-2\right.\) стъпала) има \(f_{n-1}\) начина;

◦ от (\(2 n+1\) )-то до \(3 n\)-тото (\(n-1\) стъпала) има \(f_{n}\) начина.

Така всички начини са \(f_{n+1} f_{n+1} f_{n+1}+2 f_{n} f_{n} f_{n+1}+f_{n} f_{n-1} f_{n}\).

Втори метод: Прилагаме Задача 3 за \(m=2 n\), след което заместваме

\(f_{2 n}\) и \(f_{2 n+1}\) с формулите от Задачи 2, 1:

\[ \begin{gathered} f_{n+2 n+1}=f_{n} f_{2 n}+f_{n+1} f_{2 n+1}=f_{n}^{2}\left(f_{n-1}+f_{n+1}\right)+f_{n+1}\left(f_{n}^{2}+f_{n+1}^{2}\right) \\ f_{3 n+1}=f_{n}^{2} f_{n-1}+2 f_{n}^{2} f_{n+1}+f_{n+1}^{3} \end{gathered} \]

Задача 5. Докажете, че \(f_{n+2}=1+f_{1}+f_{2}+\cdots+f_{n}\).

Решение. Има \(f_{n+2}\) начина да се изкачи стълбище с \(n+1\) стъпала, ако се изкачват по едно или по две. Има само един начин за изкачване, при който всички крачки са единични. Разбиваме множеството на останалите начини според момента, в който е направена първата двойна крачка (ПДК).

• Ако ПДК е още в началото, то остават \(n-1\) стъпала, за които има

\(f_{n}\) начина.

• Ако ПДК е след една единична крачка, то остават \(n-2\) стъпала, за които има \(f_{n-1}\) начина.

• Ако ПДК е след две единични крачки, то остават \(n-3\) стъпала, за които има \(f_{n-2}\) начина и т.н.

• Накрая, ако ПДК е след \(n-1\) единични крачки, то остават 0 стъпала, за които има \(f_{1}\) начин.

От принципа за събиране получаваме доказваното равенство.□

Задача 6. Докажете, че \(f_{2 n+1}=1+f_{2}+f_{4}+\cdots+f_{2 n}\).

Решение. Има \(f_{2 n+1}\) начина да се изкачи стълбище с \(2 n\) стъпала, ако се изкачват по едно или по две. Има само един начин за изкачване, при който всички крачки са двойни. Разбиваме множеството на останалите начини според момента, в който е направена първата единична крачка (ПЕК).

• Ако ПЕК е още в началото, то остават \(2 n-1\) стъпала, за които има

\(f_{2 n}\) начина.

• Ако ПЕК е след една двойна крачка, то остават \(2 n-3\) стъпала, за които има \(f_{2 n-2}\) начина.

• Ако ПЕК е след две двойни крачки, то остават \(2 n-5\) стъпала, за които има \(f_{2 n-4}\) начина и т.н.

• Накрая, ако ПЕК е след \(n-1\) двойни крачки, то остава 1 стъпало, за които има \(f_{2}\) начина.

От принципа за събиране получаваме доказваното равенство.□

Задача 7. Докажете, че \(f_{2 n}=f_{1}+f_{3}+\cdots+f_{2 n-1}\).

Решение. Има \(f_{2 n}\) начина да се изкачи стълбище с \(2 n-1\) стъпала, ако се изкачват по едно или по две. Да разбием множеството от възможни начини за изкачване на стълбите според позицията на първата единична крачка (ПЕК) – такава има, понеже стълбището е с нечетна дължина.

• Ако ПЕК е още в началото, то остават \(2 n-2\) стъпала, за изкачването на които има \(f_{2 n-1}\) начина.

• Ако ПЕК е след една двойна крачка, то остават \(2 n-4\) стъпала и

\(f_{2 n-3}\) начина за изкачването им т.н.

• Накрая, ако ПЕК е след \(n-1\) двойни крачки, тогава остават 0 стъпала, за изкачването на които има \(f_{1}=1\) начин.

От принципа за събиране получаваме доказваното равенство.□

Задача 8. Докажете, че за всяко \(n \geq 3\) е в сила

\[ f_{n+1}=n+(n-3) f_{1}+(n-4) f_{2}+\cdots+2 f_{n-4}+1 f_{n-3} . \]

Решение. Има \(f_{n+1}\) начина да се изкачи стълбище с \(n\) стъпала, ако се изкачват по едно или по две. Eдин възможен начин е всички крачки да са единични. Има и \(n-1\) начина за изкачване само с една двойна крачка

– да я наречем първа двойна крачка (ПДК). Всички останали изкачвания да разбием на непресичащи се подмножества според позицията на втората двойна крачка ВДК.

• Ако ВДК е от стъпало 2 до стъпало 4, то за ПДК има 1 вариант и остават \(n-4\) стъпала, които можем да изкачим по \(f_{n-3}\) начина.

• Ако ВДК е от стъпало 3 до стъпало 5, то за ПДК има 2 варианта и остават \(n-5\) стъпала, които можем да изкачим по \(f_{n-4}\) начина.

• Ако ВДК е от стъпало 4 до стъпало 6, то за ПДК има има 3 варианта и остават \(n-6\) стъпала, които можем да изкачим по \(f_{n-5}\) начина и т.н.

• Накрая, ако ВДК е от стъпало \(n-2\) до стъпало \(n\), то за ПДК има

\(n-3\) варианта и остават 0 стъпала, които изкачваме по \(f_{1}=1\) начин.

От принципа за събиране получаваме доказваното равенство.□

Забележка. Записването на равенството от Задача 8 в съкратен вид

\[ f_{n+1}=n+\sum_{i=1}^{n-3}(n-2-i) f_{i} \]

сочи, че то всъщност е вярно за всички естествени \(n\). Наистина, при \(n \leq 3\) сумата е празна, а същевременно \(f_{2}=1\) и \(f_{3}=2\).

Задача 9. Докажете, че за всяко \(n \geq 2\) е в сила

\[ f_{n+1}=\tfrac{n^{2}-3 n+6}{2}+\sum_{i=1}^{n-5}\binom{n-3-i}{2} f_{i} \]

В частност, ако \(2 \leq n \leq 5\), то \(f_{n+1}=\tfrac{n^{2}-3 n+6}{2}\).

Решение. Има \(f_{n+1}\) начина да се изкачи стълбище с \(n\) стъпала, ако се изкачват по едно или по две. Един възможен начин е всички крачки да са единични. Имаме \(n-1\) начина за изкачване само с една двойна крачка. Начините за изкачване с две двойни крачки са \(\binom{n-2}{2}\). За тези три подмножества получаваме общо

\[ n+\tfrac{(n-2)(n-3)}{2}=\tfrac{2 n+n^{2}-3 n-2 n+6}{2}=\tfrac{n^{2}-3 n+6}{2} \]

начина. Разбиваме останалите начини на непресичащи се подмножества според мястото на третата двойна крачка ТДК.

• Ако ТДК е от стъпало 4 до стъпало 6, то за първите две двойни крачки има 1 вариант и остават \(n-6\) стъпала, за изкачването на които има \(f_{n-5}\) начина.

• Ако ТДК е от стъпало 5 до стъпало 7, то до стъпало 5 има 3 крачки, от които 2 са двойни, така че за местата им има \(\binom{3}{2}\) начина и остават

\(n-7\) стъпала или \(f_{n-6}\) начина.

• Ако ТДК е от стъпало 6 до стъпало 8, то до стъпало 6 има 4 крачки, от които 2 двойни, така че за местата им има \(\binom{4}{2}\) начина и остават \(n-8\) стъпала или \(f_{n-7}\) начина и т.н.

• Накрая, ако TДК е от стъпало \(n-2\) до стъпало \(n\), то до стъпало

\(n-2\) има \(n-4\) крачки, от които 2 двойни, така че за местата им има

\(\binom{n-4}{2}\) начина и остават 0 стъпала или \(f_{1}=1\) начин.

От принципа за събиране получаваме доказваното равенство.□

Задача 10. Докажете, че за всяко \(n \geq 3\) е в сила

\[ f_{n+1}=\tfrac{n^{3}-9 n^{2}+38 n-42}{6}+\sum_{i=1}^{n-7}\binom{n-4-i}{3} f_{i} . \]

В частност, ако \(3 \leq n \leq 7\), то \(f_{n+1}=\tfrac{n^{3}-9 n^{2}+38 n-42}{6}\).

Решение. Има \(f_{n+1}\) начина да се изкачи стълбище с \(n\) стъпала, ако се изкачват по едно или по две. От решението на Задача 9. знаем, че начините с не повече от две двойни крачки са \(\tfrac{1}{2}\left(n^{2}-3 n+6\right)\). Добавяйки към тях и възможните \(\binom{n-3}{2}\) начина за изкачване с три двойни крачки, получаваме

\[ \tfrac{n^{2}-3 n+6}{2}+\tfrac{(n-3)(n-4)(n-5)}{6}=\tfrac{n^{3}-9 n^{2}+38 n-42}{6} \]

начина. Разбиваме останалите начини на непресичащи се подмножества според мястото на четвъртата двойна крачка (ЧДК).

• Ако ЧДК е от стъпало 6 до стъпало 8, то за първите три двойни крачки има 1 вариант и остават \(n-8\) стъпала, за изкачването на които има \(f_{n-7}\) начина.

• Ако ЧДК е от стъпало 7 до стъпало 9, то до стъпало 7 има 4 крачки, от които 3 са двойни, така че за местата им има \(\binom{4}{3}\) начина и остават

\(n-9\) стъпала: \(f_{n-8}\) начина.

• Ако ЧДК е от стъпало 8 до стъпало 10, то до стъпало 8 има 5 крачки, от които 3 двойни, така че за местата им има \(\binom{5}{3}\) начина и остават \(n-10\) стъпала: \(f_{n-9}\) начина и т.н.

• Накрая, ако ЧДК е от стъпало \(n-2\) до стъпало \(n\), то до стъпало

\(n-2\) има \(n-5\) крачки, от които 3 двойни, така че за местата им има

\(\binom{n-5}{3}\) начина и остават 0 стъпала: \(f_{1}=1\) начин.

От принципа за събиране получаваме доказваното равенство.□

Задача 11. Докажете, че за всяко \(n \geq k-1\) е в сила

\[ f_{n+1}=\sum_{i=0}^{k-1}\binom{n-i}{i}+\sum_{i=1}^{n-2 k+1}\binom{n-k-i}{k-1} f_{i} . \]

Решение. Има \(f_{n+1}\) начина да се изкачи стълбище с \(n\) стъпала, ако се изкачват по едно или по две. Както в предходните задачи установяваме, че броят на начините с по-малко от \(k\) двойни крачки е \(\sum_{i=0}^{k-1}\binom{n-i}{i}\).

Разбиваме останалите начини на непресичащи се подмножества според мястото на \(k\)-тата двойна крачка (КДК).

• Ако КДК е от стъпало \(2 k-2\) до стъпало \(2 k\), то за първите \(k-1\) двойни крачки има 1 вариант и остават \(n-2 k\) стъпала, за изкачването на които има \(f_{n-2 k+1}\) начина.

• Ако КДК е от \(2 k-1\) до стъпало \(2 k+1\), то до стъпало \(2 k-1\) има

\(k\) крачки, от които \(k-1\) са двойни, така че за местата им има \(\binom{k}{k-1}\) начина и остават \(n-2 k-1\) стъпала: \(f_{n-2 k}\) начина.

• Ако КДК е от стъпало \(2 k\) до стъпало \(2 k+2\), то до стъпало \(2 k\) има

\(k+1\) крачки, от които \(k-1\) двойни, така че за местата им има \(\binom{k+1}{k-1}\) начина и остават \(n-2 k-2\) стъпала: \(f_{n-2 k-1}\) начина и т.н.

• Накрая, ако KДК е от стъпало \(n-2\) до стъпало \(n\), то до стъпало

\(n-2\) има \(n-k-1\) крачки, от които \(k-1\) двойни, така че за местата им има \(\binom{n-k-1}{k-1}\) начина и остават 0 стъпала: \(f_{1}=1\) начин.

От принципа за събиране получаваме доказваното равенство.□

Задача 12. Докажете, че \(f_{n+1}=\sum_{i=0}^{\lfloor n / 2\rfloor}\binom{n-i}{i}\).

Решение. Има \(f_{n+1}\) начина да се изкачи стълбище с \(n\) стъпала, ако се изкачват по едно или по две. Разбиваме множеството на начините според броя \(i \leq\lfloor n / 2\rfloor\) на участващите в тях двойни крачки. В подмножеството на изкачванията с \(i\) двойни крачки общият брой крачки е \(n-i\) и можем да изберем местата на двойните крачки по \(\binom{n-i}{i}\) начина. От принципа за събиране следва доказваното равенство.□

Задача 13. Докажете, че

\[ f_{2 n+1}=1+n f_{1}+(n-1) f_{3}+\cdots+2 . f_{2 n-3}+1 . f_{2 n-1} . \]

Решение. Има \(f_{2 n+1}\) начина да се изкачи стълбище с \(2 n\) стъпала, ако се изкачват по едно или по две. Тъй като броят на стъпалата е четен, има един начин за изкачване само с двойни крачки. Поради същата причина, ако в изкачването има единична крачка (ПЕК), то непременно ще има и поне още една единична крачка. Затова да разбием множеството от оставащите начини на подмножества според позицията на втората единична крачка (ВЕК).

• Ако ВЕК е от стъпало 1 до стъпало 2, то за ПЕК има 1 възможност и остават \(2 n-2\) стъпала, за изкачване на които има \(f_{2 n-1}\) начина.

• Ако преди ВЕК има една двойна крачка, то ВЕК е от стъпало 3 до стъпало 4. Тогава за ПЕК има 2 възможности и остават \(2 n-4\) стъпала, които изкачваме по \(f_{2 n-3}\) начина.

• Ако преди ВЕК има две двойни крачки, то ВЕК е от стъпало 5 до стъпало 6. Тогава за ПЕК има 3 възможности и остават \(2 n-6\) стъпала, които изкачваме по \(f_{2 n-5}\) начина и т.н.

• Накрая, ако преди ВЕК има \(n-1\) двойни крачки, то ВEК е от стъпало \(2 n-1\) до стъпало \(2 n\). Тогава за ПEК има \(n\) възможности и остават 0 стъпала, които изкачваме по \(f_{1}=1\) начин.

От принципа за събиране получаваме доказваното равенство.□

Задача 14. Докажете, че

\[ f_{2 n+2}=n+1+n f_{2}+(n-1) f_{4}+\cdots+2 . f_{2 n-2}+1 . f_{2 n} . \]

Решение. Има \(f_{2 n+2}\) начина да се изкачи стълбище с \(2 n+1\) стъпала, ако се изкачват по едно или по две. Тъй като стълбището е с нечетна дължина, то във всяко изкачване има поне една единична крачка. Има \(n+1\) начина за изкачване с точно 1 единична крачка. Разбиваме множеството на останалите изкачвания според позицията на ВЕК.

• Ако ВЕК е от стъпало 1 до стъпало 2, то за ПЕК има 1 възможност и остават \(2 n-1\) стъпала, които изкачваме по \(f_{2 n}\) начина.

• Ако преди ВЕК има една двойна крачка, то ВЕК е от стъпало 3 до стъпало 4. Тогава за ПЕК има 2 възможности и остават \(2 n-4\) стъпала, които изкачваме по \(f_{2 n-3}\) начина.

• Ако преди ВЕК има две двойни крачки, то ВЕК е от стъпало 5 до стъпало 6. Тогава за ПЕК има 3 възможности и остават \(2 n-6\) стъпала, които изкачваме по \(f_{2 n-5}\) начина и т.н.

• Накрая, ако преди ВЕК има \(n-1\) двойни крачки, то ВEК е от стъпало \(2 n-1\) до стъпало \(2 n\). Тогава за ПEК има \(n\) възможности и остава 1 стъпало, което изкачваме по \(f_{2}\) начина.

От принципа за събиране получаваме доказваното равенство.□

Задача 15. Докажете, че

\[ f_{2 n}=n+\sum_{i=1}^{n-1}\binom{n+1-i}{2} f_{2 i-1} . \]

Решение. Има \(f_{2 n}\) начина да се изкачи стълбище с \(2 n-1\) стъпала, ако се изкачват по едно или по две. Тъй като стълбището е с нечетна дължина, то във всяко изкачване има нечетен брой единични крачки. Съществуват

\(n\) начина за изкачване с точно 1 единична крачка. Разбиваме множеството на останалите изкачвания според позицията на третата единична крачка (ТЕК).

• Ако ТЕК е от стъпало 2 до стъпало 3, то преди нея има само 1 възможност (две ЕК) и остават \(2 n-4\) стъпала, за изкачването на които има \(f_{2 n-3}\) начина.

• Ако преди ТЕК има една двойна крачка, то ТЕК е от стъпало 4 до стъпало 5. Тогава до стъпало 4 има две единични и една двойна крачка, съответно \(\binom{3}{2}\) възможности. Остават \(2 n-6\) стъпала, които изкачваме по \(f_{2 n-5}\) начина.

• Ако преди ТЕК има две двойни крачки, то ТЕК е от стъпало 6 до стъпало 7. Тогава до стъпало 6 има две единични и две двойни крачки, съответно \(\binom{4}{2}\) възможности. Остават \(2 n-8\) стъпала, които изкачваме по \(f_{2 n-7}\) начина и т.н.

• Накрая, ако преди ТЕК има \(n-2\) двойни крачки, то ТEК е от стъпало

\(2 n-2\) до стъпало \(2 n-1\). Тогава до стъпало \(2 n-2\) има \(n\) крачки, от които

2 единични или \(\binom{n}{2}\) възможности. Остават 0 стъпала или \(f_{1}=1\) начин.

От принципа за събиране получаваме доказваното равенство.□

Задача 16. Докажете, че

\[ f_{2 n+1}=\tfrac{n^{2}+n+2}{2}+\sum_{i=1}^{n-1}\binom{n+1-i}{2} f_{2 i} . \]

Решение. Има \(f_{2 n+1}\) начина да се изкачи стълбище с \(2 n\) стъпала, ако се качват по едно или по две. Тъй като стълбището е с четна дължина, единичните крачки са четен брой. Има един начин за изкачване само с двойни крачки и \(\binom{n+1}{2}\) начина с 2 единични крачки, общо

\(1+\tfrac{n(n+1)}{2}=\tfrac{n^{2}+n+2}{2}\) начина. Да разбием множеството на останалите изкачвания според позицията на ТЕК.

• Ако ТЕК е от стъпало 2 до стъпало 3, то преди нея има само 1 възможност – две ЕК, и остават \(2 n-3\) стъпала, за изкачването на които има \(f_{2 n-2}\) начина.

• Ако преди ТЕК има една двойна крачка, то ТЕК е от стъпало 4 до стъпало 5. Тогава до стъпало 4 има две единични и една двойна крачка и \(\binom{3}{2}\) възможности. Остават \(2 n-5\) стъпала, които изкачваме по \(f_{2 n-4}\) начина.

• Ако преди ТЕК има две двойни крачки, то ТЕК е от стъпало 6 до стъпало 7. Тогава до стъпало 6 има две единични и две двойни крачки и \(\binom{4}{2}\) възможности. Остават \(2 n-7\) стъпала, които изкачваме по \(f_{2 n-6}\) начина и т.н.

• Накрая, ако преди ТЕК има \(n-2\) двойни крачки, то ТEК е от стъпало \(2 n-2\) до стъпало \(2 n-1\). Тогава до стъпало \(2 n-2\) има \(n\) крачки, от които 2 единични или \(\binom{n}{2}\) възможности. Остават 1 стъпало или \(f_{2}\) начина.

От принципа за събиране получаваме доказваното равенство.□

Задача 17. Докажете, че

\[ f_{2 n+1}=\tfrac{n^{2}+n+2}{2}+\sum_{i=1}^{n-1}\binom{n+2-i}{3} f_{2 i-1} . \]

Решение. Има \(f_{2 n+1}\) начина да се изкачи стълбище с \(2 n\) стъпала, ако се изкачват по едно или по две. Стълбището е с четна дължина, така че единичните крачки са четен брой. Има един начин за изкачване само с двойни крачки и \(\binom{n+1}{2}\) начина с 2 единични крачки, общо

\(1+\tfrac{n(n+1)}{2}=\tfrac{n^{2}+n+2}{2}\) начина. Да разбием множеството на останалите изкачвания според позицията на четвъртата единична крачка (ЧЕК).

• Ако ЧЕК е от стъпало 3 до стъпало 4, то преди нея има само 1 възможност – три ЕК, и остават \(2 n-4\) стъпала, за изкачването на които има \(f_{2 n-3}\) начина.

• Ако преди ЧЕК има една двойна крачка, то ЧЕК е от стъпало 5 до стъпало 6. Тогава до стъпало 5 има три единични и една двойна крачка и \(\binom{4}{3}\) възможности. Остават \(2 n-6\) стъпала, които изкачваме по \(f_{2 n-5}\) начина.

• Ако преди ЧЕК има две двойни крачки, то ЧЕК е от стъпало 7 до стъпало 8. Тогава до стъпало 7 има три единични и две двойни крачки и

\(\binom{5}{3}\) възможности. Остават \(2 n-8\) стъпала, т.е. \(f_{2 n-7}\) начина и т.н.

• Накрая, ако преди ЧЕК има \(n-2\) двойни крачки, то ЧEК е от стъпало \(2 n-1\) до стъпало \(2 n\). Тогава до стъпало \(2 n-1\) има \(n+1\) крачки, от които 3 единични или \(\binom{n+1}{3}\) възможности. Остават 0 стъпала или

\(f_{1}=1\) начин.

От принципа за събиране получаваме доказваното равенство.□

Задача 18. Докажете, че

\[ f_{2 n+2}=\tfrac{(n+1)\left(n^{2}+n+6\right)}{6}+\sum_{i=1}^{n-1}\binom{n+2-i}{3} f_{2 i} \]

Решение. Има \(f_{2 n+2}\) начина да се изкачи стълбище с \(2 n+1\) стъпала, ако се изкачват по едно или по две. Стълбището е с нечетна дължина, така че единичните крачки са нечетен брой. Сред начините за изкачване има

\(n+1\) с една единична крачка и \(\binom{n+1}{3}\) с 3 единични крачки, общо

\[ n+1+\tfrac{n(n+1)(n+2)}{6}=\tfrac{(n+1)\left(n^{2}+n+6\right.}{6} \]

начина. Да разбием множеството на останалите изкачвания според позицията на ЧЕК.

• Ако ЧЕК е от стъпало 3 до стъпало 4, то преди нея има само 1 възможност – три ЕК, и остават \(2 n-3\) стъпала, за изкачването на които има \(f_{2 n-2}\) начина.

• Ако преди ЧЕК има една двойна крачка, то ЧЕК е от стъпало 5 до стъпало 6. Тогава до стъпало 5 има три единични и една двойна крачка и \(\binom{4}{3}\) възможности. Остават \(2 n-5\) стъпала, които изкачваме по \(f_{2 n-4}\) начина.

• Ако преди ЧЕК има две двойни крачки, то ЧЕК е от стъпало 7 до стъпало 8. Тогава до стъпало 7 има три единични и две двойни крачки и \(\binom{5}{3}\) възможности. Остават \(2 n-7\) стъпала, които изкачваме по \(f_{2 n-6}\) начина и т.н.

• Накрая, ако преди ЧЕК има \(n-2\) двойни крачки, то ЧEК е от стъпало \(2 n-1\) до стъпало \(2 n\). Тогава до стъпало \(2 n-1\) има \(n+1\) крачки, от които 3 единични, за което има \(\binom{n+1}{3}\) възможности. Остава 1 стъпало или \(f_{2}\) начина.

От принципа за събиране получаваме доказваното равенство.□

Задача 19. Докажете, че

\[ f_{2 n+2}=\sum_{i=1}^{k}\binom{n+i}{2 i-1}+\sum_{i=1}^{n+1-k}\binom{n+k-i}{2 k-1} f_{2 i} . \]

Решение. При \(k \gt n\) равенството е в сила, защото втората сума е 0 поради липса на събираеми, а в първата събираемите имат принос само когато

\(n+i \geq 2 i-1\), т.е. при \(i \leq n+1\). В резултат на това

\[ f_{2 n+2}=\sum_{j=0}^{n}\binom{2 n+1-j}{j}=\sum_{i=1}^{n+1}\binom{n+i}{n+1-i}=\sum_{i=1}^{n+1}\binom{n+i}{2 i-1} \]

според Задача 12 за \(2 n+1\) вместо \(n\) поради \(\left\lfloor\tfrac{2 n+1}{2}\right\rfloor=n\).

Ще покажем, че равенството е в сила и при \(k \leq n\).

Има \(f_{2 n+2}\) начина да се изкачи стълбище с \(2 n+1\) стъпала, ако се изкачват по едно или по две. Стълбището е с нечетна дължина, така че единичните крачки са нечетен брой. За броя на изкачванията \(1,3,5, \ldots, 2 k-1\) единични крачки (и съответно общ брой крачки \(n+1, n+2, \ldots, n+k\) ) имаме \(\sum_{i=1}^{k}\binom{n+i}{2 i-1}\) начина. Да разбием множеството от останалите изкачвания на подмножества според позицията на \(2 k\)-тата единична крачка (2КЕК).

• Ако 2КЕК е от стъпало \(2 k-1\) до стъпало \(2 k\), тогава за първите \(2 k-1\) единични крачки има само 1 възможност и остават \(2 n+1-2 k\) стъпала, за изкачването на които има \(f_{2 n+2-2 k}\) начина.

• Ако преди 2КЕК има една двойна крачка, то 2КЕК е от стъпало

\(2 k+1\) до стъпало \(2 k+2\). Тогава до стъпало \(2 k+1\) има \(2 k\) крачки, от които

\(2 k-1\) единични, и съответно \(\binom{2 k}{2 k-1}\) възможности. Остават \(2 n-1-2 k\) стъпала, които изкачваме по \(f_{2 n-2 k}\) начина.

• Ако преди 2КЕК има две двойни крачки, то 2КЕК е от стъпало \(2 k+3\) до стъпало \(2 k+4\). Тогава до стъпало \(2 k+3\) има \(2 k+1\) крачки, от които

\(2 k-1\) единични, и съответно \(\binom{2 k+1}{2 k-1}\) възможности. Остават \(2 n-3-2 k\) стъпала, които изкачваме по \(f_{2 n-2-2 k}\) начина и т.н.

• Накрая, ако преди 2КЕК има \(n-k\) двойни крачки, то 2КЕК е от стъпало \(2 n-1\) до стъпало \(2 n\). Тогава до стъпало \(2 n-1\) има \(n+k-1\) крачки, от които \(2 k-1\) единични или \(\binom{n+k-1}{2 k-1}\) възможности. Остава

1 стъпало или \(f_{2}\) начина.

От принципа за събиране доказваното равенство.□

По начин, подобен на този в Задача 19, могат да се решат и следващите три задачи:

Задача 20. Докажете, че

\[ f_{2 n+1}=\sum_{i=0}^{k-1}\binom{n+i}{2 i}+\sum_{i=1}^{n+1-k}\binom{n+k-i}{2 k-1} f_{2 i-1} \]

Задача 21. Докажете, че

\[ f_{2 n+1}=\sum_{i=0}^{k}\binom{n+i}{2 i}+\sum_{i=1}^{n+1-k}\binom{n+k-i}{2 k} f_{2 i} . \]

Задача 22. Докажете, че

\[ f_{2 n}=\sum_{i=0}^{k-1}\binom{n+i}{2 i+1}+\sum_{i=1}^{n-k}\binom{n+k-i}{2 k} f_{2 i-1} \]

4. Заключение

Двукратното броене традиционно се приема с ентусиазъм от учениците със задълбочен интерес към математиката, често дори изразяващо се в „уау“-ефект при осъзнаването на това как дадена реална ситуация може да моделира и да докаже комбинаторен факт. Това се потвърждава и от апробирането в реална група от мотивирани ученици на тъждества сред дадените по-горе, както и на други подобни, например от (Kortezov 2020).

Представеният тук метод позволява на учениците да запомнят трайно и точно разнообразни комбинаторни тъждества, за които чисто формалното запомняне е предизвикателство, както и да задават съдържателни въпроси и да генерират нови идеи.

ЛИТЕРАТУРА

АЛФУТОВА Н.Б., УСТИНОВ, А.В., 2002. Алгебра и теория чисел. Сборник задач для математических школ, МЦНМО, Москва, стр. 264. ISBN 5-94057-038-0.

КОРТЕЗОВ, И., 2019. Състезателни теми от математически лагери. т. 1, Как да броим, без да броим, Второ преработено и допълнено издание, Фастумпринт, стр. 180. ISBN 978-619-7223-67-5.

КОРТЕЗОВ, И., 2020. Метод на децата в блока. Математика и информатика, T. 63, № 5, стр. 527 – 537. ISSN 1310–2230.

REFERENCES

DEBNATH, L., 2011. A short history of the Fibonacci and golden numbers with their applications, International J. Math. Ed. Sci. Tech, vol. 42, no. 3, pp. 337 – 367. ISSN 1464-5211 (Online).

HOGGATT, V.E., 1969. Fibonacci and Lucas Numbers, Houghton Mifflin Company, Boston, ISBN 9789991205311.

KOSHY, T., 2001. Fibonacci and Lucas Numbers with Applications, John Wiley and Sons, Proc., New York–Toronto. ISBN 9780471399698.

ALFUTOVA, N.B., USTINOV, A.V., 2002. Algebra and number theory. Collection of problems for mathematical schools, Moscow, MCCME, p. 264 (in Russian). ISBN 5-94057-038-0.

KORTEZOV, I., 2019. Contest topics from math camps. Vol. 1, How to count without counting, \(2^{\text {nd }}\) Ed., Fastumprint, p. 180 (in Bulgarian). ISBN 978-619-7223-67-5.

KORTEZOV, I., 2020. Method of the Children in the Skyscraper. Mathematics and Informatics, vol. 63, no. 5, pp. 527 – 537. ISSN 1310–2230.