To climb the stairs, Evariste can take steps of 1 stair and steps of 2 stairs. In how many different ways can he climb a staircase with $n$ stairs?
To start, let's denote $u_{n}$ as the number we are looking for. The problem seems to ask for an explicit formula for $u_{n}$, but before that, let's find what is called a recurrence relation, which is an expression of $u_{n}$ in terms of the previous terms $u_{k}$ $(k<n)$.

For $n \geq 2$, we distinguish two cases: either Evariste starts with a step of 1 stair, in which case he has $u_{n-1}$ ways to climb the remaining $n-1$ stairs; or he starts with a step of 2 stairs and has $u_{n-2}$ possibilities to finish the staircase. Thus, we obtain the relation $u_{n}=u_{n-1}+u_{n-2}$.

Since this recurrence relation involves the two terms preceding $u_{n}$, we need to initialize our sequence with the first two terms. When there are 0 or 1 stairs, Evariste has only one way to proceed. Therefore, we have $u_{0}=1$ and $u_{1}=1$.

It turns out that the sequence thus defined is a well-known recurrence sequence: the famous Fibonacci sequence! I leave it to the readers who wish to know more to inform themselves, derive the explicit formula for $u_{n}$, or rediscover the construction of the golden ratio with a ruler and compass...

## 4 Friday, May 19th morning: Wassim Trabelsi

## Basic Calculations

Proposition 1 (Simple Factorization). $k \times(a+b)=k \times a+k \times b$

![](https://cdn.mathpix.com/cropped/2024_05_10_da6e2ad19b1b4e3d33dcg-041.jpg?height=366&width=659&top_left_y=782&top_left_x=901)

Proof.

Proposition 2 (Rectangle Factorization). $(a+b) \times(c+d)=a c+a d+b c+b d$

![](https://cdn.mathpix.com/cropped/2024_05_10_da6e2ad19b1b4e3d33dcg-041.jpg?height=564&width=856&top_left_y=1434&top_left_x=819)

Proof.

Proposition 3 (Remarkable Identities).

$$
\begin{gathered}
(a+b)^{2}=a^{2}+2 a b+b^{2} \\
(a-b)^{2}=a^{2}-2 a b+b^{2} \\
(a+b)(a-b)=a^{2}-b^{2} \\
(a+b)^{3}=a^{3}+3 a^{2} b+3 a b^{2}+b^{3}
\end{gathered}
$$

Proof.

$$
(a+b)^{2}=(a+b)(a+b)=a^{2}+a b+b a+b^{2}=a^{2}+2 a b+b^{2}
$$

More generally, the Pascal's triangle can be used to obtain the coefficients of the remarkable expansion of $(a+b)^{n}$.

In practice, these formulas are also useful in arithmetic problems with integers: a factored expression reveals divisors.

Proposition 4 (Calculations with Powers).

$$
\begin{gathered}
a^{m} \times a^{n}=a^{m+n} \\
\frac{a^{m}}{a^{n}}=a^{m-n} \\
\left(a^{m}\right)^{n}=a^{m n}
\end{gathered}
$$

## Some Classical Sums