## 42. Barrels

In how many ways can a 10-liter barrel be emptied using two containers with capacities of 1 liter and 2 liters?
42. Let $u_{n}$ be the number of ways to empty a barrel of capacity $n$ liters using two vessels of capacity 1 and 2 liters.

A barrel of $n$ liters will be emptied if we first use either the 1-liter vessel [and then we need to choose $(n-1)$ liters more from the barrel], or the 2-liter vessel [and then we need to choose $(n-2)$ liters more]. This gives us the recurrence relation

$$
u_{n}=u_{n-1}+u_{n-2}
$$

Obviously, $u_{0}=1, u_{1}=1$.

We obtain sequentially

$$
\begin{array}{ll}
u_{2}=2, & u_{5}=13, \\
u_{3}=3, & u_{7}=21, \\
u_{4}=5, & u_{8}=34, \\
u_{5}=8, & u_{9}=55, \\
& u_{10}=89 .
\end{array}
$$

Thus, there are 89 ways to empty a barrel of capacity 10 liters using the two specified vessels ${ }^{1}$.