Consider the sequence $\left(a_{n}\right)$ with the first term $a_{1}=1$ and defined by the following relation: For any positive integer $n$,

$$
a_{n}=a_{\left\lfloor\frac{n}{2}\right\rfloor}+a_{\left\lceil\frac{n}{2}\right\rceil}
$$

Express $a_{n}$ as a function of $n$.
We calculate the first terms: $a_{2}=a_{1}+a_{1}=2$ and $a_{3}=a_{1}+a_{2}=3$. We start to wonder if $a_{n}=n$ for all strictly positive integers $n$. We proceed by strong induction on $n$. The base case being already done, we tackle the inductive step. Since $a_{k}=k$ for all integers $k \leq n$, we have $a_{n+1}=a_{\left\lfloor\frac{n}{2}\right\rfloor}+a_{\left\lceil\frac{n}{2}\right\rceil}=\left\lfloor\frac{n}{2}\right\rfloor+\left\lceil\frac{n}{2}\right\rceil$ To show that $\left\lceil\frac{n}{2}\right\rceil+\left\lfloor\frac{n}{2}\right\rfloor=n+1$, we can study the parity of $n+1$ or we can also use the inequalities related to the floor and ceiling functions to obtain $n<\left\lceil\frac{n}{2}\right\rceil+\left\lfloor\frac{n}{2}\right\rfloor<n+2$ and conclude.