## Task 4 - 280614

The staircase in the figure consists of four steps. To climb this four-step staircase, one can either step up exactly one or exactly two steps at a time. (One possible sequence of steps is, for example, 1, 3, 4.)

a) List all possible step sequences for this staircase! How many are there in total?

![](https://cdn.mathpix.com/cropped/2024_06_06_b85a894aa8dbf722a7b3g-0264.jpg?height=217&width=329&top_left_y=668&top_left_x=1429)

b) List all possible step sequences for a three-step staircase, similarly for a two-step staircase, and for a one-step staircase!

c) Someone claims: "The number of all possible step sequences for a four-step staircase can be found through a simple calculation if one knows the number of all possible step sequences for a three-step staircase and the number of all possible step sequences for a two-step staircase." Provide such a simple calculation! Write it in the form of an equation!

d) Write a corresponding equation that allows the number of all possible step sequences for a three-step staircase to be calculated from the corresponding numbers for a two-step and a one-step staircase!

e) Why do the relationships found in c) and d) hold?

f) Give the number of all possible step sequences for a five-step and a six-step staircase!
a) All possible step sequences for a four-step staircase are:

$$
1,2,3,4 ; \quad 1,2,4 ; \quad 1,3,4 ; \quad 2,3,4 ; \quad 2,4
$$

b) All possible step sequences for a three-step staircase are:

$$
1,2,3 ; \quad 1,3 ; \quad 2,3
$$

All possible step sequences for a two-step staircase are: 1,2; 2. For a one-step staircase, there is exactly the step sequence 1.

c) The number of step sequences for a four-step staircase is equal to the sum of the number of step sequences for a three-step and a two-step staircase: $5=3+2$.

d) The number of step sequences for a three-step staircase is equal to the sum of the number of step sequences for a two-step and a one-step staircase: $3=2+1$.

e) To climb a four-step staircase in the given manner, one can either take one step first and then have three steps left, or take two steps first and then have two steps left.

In the first case, the number of possible continuations is equal to the number of step sequences for a three-step staircase, and in the second case, it is equal to the number of step sequences for a two-step staircase. Therefore, the total number of possible step sequences for a four-step staircase is equal to the sum of the number of possible step sequences for a three-step and a two-step staircase.

f) Accordingly, it follows: The equation $8=5+3$ leads to the number 8 of step sequences for a five-step staircase; the equation $13=8+5$ leads to the number 13 of step sequences for a six-step staircase.

Solutions of the first round 1988 taken from [5]

### 3.29.2 Second Round 1988, Class 6