Numbers in itself

My hobby is teaching mathematics and computer science to schoolchildren. In this process, the issue of motivation is very important, so you have to be very careful about the quality of the material feed. After going through various methods of reading the material, the idea of ​​the project “One Task” was born, in which, using the example of solving only one task, a lecture was given with the presentation of various new materials. So, I demonstrate the first material of this project.

Task: there are tiles of 1x1 and 1x2 meters. How many ways are there to pave a rectangle of 1x15 meters with these tiles?

A person without experience in solving such combinatorial problems is usually not easy to offer a solution to this problem. Therefore, it is worthwhile to reduce it to a simpler one in order to obtain a working hypothesis. Let's start sorting out the ways of paving smaller rectangles.
A 1x1 rectangle can be tiled in only one way. Rectangle 1x2 - two. Create a table for simpler rectangles:

The size	Number of options
1x1	one
1x2	2
1x3	3
1x4	five
1x5	eight

')
Just in case, we list all the options for a 1x5 rectangle, where the number 1 is a 1x1 tile, the number 2 is a 1x2 tile:

eleven
2. 11 2
3. 111 12 21
4. 1111 112 121 211 22
5. 11111 1112 1121 1211 2111 122 212 221

It is easy to see that in the table in the second column are the Fibonacci numbers. Their appearance is clearly not accidental. Let's think about where they can come from.
Imagine that we are tiling a rectangle from left to right. Then you can get 1xN rectangle by adding 1x1 tile to 1x rectangle (N-1) or 1x2 tile to 1x rectangle (N-2). This means that each tiling 1x (N-1) and 1x (N-2) corresponds to one tiling 1x (N). If we denote the number of tiling options for a rectangle 1xN by P (N), we obtain the formula P (N) = P (N-1) + P (N-2), which is the formula of Fibonacci numbers.

Let's now try to write a program that would calculate the Fibonacci numbers. Obviously, the formula of these numbers is recurrent, so we solve the problem in two ways: by loop and through recursion.

 program Project2;
 {$ APPTYPE CONSOLE}
 uses
   SysUtils;
 var a: array [1..15] of integer;
 i: integer;
 function p (n: integer): integer;
 begin
   if n <3 then p: = n else p: = p (n-1) + p (n-2);
 end;
 begin
   a [1]: = 1;
   a [2]: = 2;
   for i: = 3 to 15 do a [i]: = a [i-1] + a [i-2];
   writeln (a [15]);
   writeln (p (15));
   readln;
 end.

And now let's calculate how many times in this algorithm the recursive function is called for each argument. Let p (n) be the number of calls to p with argument n. Obviously, p (15) = 1 and p (14) = 1. But p (n) = p (n + 1) + (n + 2). That is, we again get all the same Fibonacci sequence. The only exception is p (1) = p (3). Thus, we have proved a remarkable fact: the complexity of the recursive algorithm for calculating Fibonacci numbers is measured by the sum of the Fibonacci numbers.