26. (ITA) For every integer $n \geq 2$ determine the minimum value that the sum $a_{0}+a_{1}+\cdots+a_{n}$ can take for nonnegative numbers $a_{0}, a_{1}, \ldots, a_{n}$ satisfying the condition  $$ a_{0}=1, \quad a_{i} \leq a_{i+1}+a_{i+2} \quad \text { for } i=0, \ldots, n-2 $$  ### 3.39 The Thirty-Ninth IMO
26. Let us first examine the case that all the inequalities in the problem are actually equalities. Then \(a_{n-2}=a_{n-1}+a_{n}, a_{n-3}=2 a_{n-1}+a_{n}, \ldots, a_{0} = F_{n} a_{n-1} + F_{n-1} a_{n} = 1\), where \(F_{n}\) is the \(n\)th Fibonacci number. Then it is easy to see (from \(F_{1} + F_{2} + \cdots + F_{k} = F_{k+2}\)) that \(a_{0} + \cdots + a_{n} = (F_{n+2} - 1) a_{n-1} + F_{n+1} a_{n} = \frac{F_{n+2} - 1}{F_{n}} + \left(F_{n+1} - \frac{F_{n-1} (F_{n+2} - 1)}{F_{n}}\right) a_{n}\). Since \(\frac{F_{n-1} (F_{n+2} - 1)}{F_{n}} \leq F_{n+1}\), it follows that \(a_{0} + a_{1} + \cdots + a_{n} \geq \frac{F_{n+2} - 1}{F_{n}}\), with equality holding if and only if \(a_{n} = 0\) and \(a_{n-1} = \frac{1}{F_{n}}\). We denote by \(M_{n}\) the required minimum in the general case. We shall prove by induction that \(M_{n} = \frac{F_{n+2} - 1}{F_{n}}\). For \(M_{1} = 1\) and \(M_{2} = 2\) it is easy to show that the formula holds; hence the inductive basis is true. Suppose that \(n > 2\). The sequences \(1, \frac{a_{2}}{a_{1}}, \ldots, \frac{a_{n}}{a_{1}}\) and \(1, \frac{a_{3}}{a_{2}}, \ldots, \frac{a_{n}}{a_{2}}\) also satisfy the conditions of the problem. Hence we have 
\[ a_{0} + \cdots + a_{n} = a_{0} + a_{1} \left(1 + \frac{a_{2}}{a_{1}} + \cdots + \frac{a_{n}}{a_{1}}\right) \geq 1 + a_{1} M_{n-1} \]
and 
\[ a_{0} + \cdots + a_{n} = a_{0} + a_{1} + a_{2} \left(1 + \frac{a_{3}}{a_{2}} + \cdots + \frac{a_{n}}{a_{2}}\right) \geq 1 + a_{1} + a_{2} M_{n-2} \]
Multiplying the first inequality by \(M_{n-2} - 1\) and the second one by \(M_{n-1}\), adding the inequalities and using that \(a_{1} + a_{2} \geq 1\), we obtain \((M_{n-1} + M_{n-2} + 1)(a_{0} + \cdots + a_{n}) \geq M_{n-1} M_{n-2} + M_{n-1} + M_{n-2} + 1\), so 
\[ M_{n} \geq \frac{M_{n-1} M_{n-2} + M_{n-1} + M_{n-2} + 1}{M_{n-1} + M_{n-2} + 1} \]
Since \(M_{n-1} = \frac{F_{n+1} - 1}{F_{n-1}}\) and \(M_{n-2} = \frac{F_{n} - 1}{F_{n-2}}\), the above inequality easily yields \(M_{n} \geq \frac{F_{n+2} - 1}{F_{n}}\). However, we have shown above that equality can occur; hence \(\frac{F_{n+2} - 1}{F_{n}}\) is indeed the required minimum.