91Ó°ÊÓ

What is wrong with the following inductive proof of "all horses are the same color."? Theorem Let \(H\) be a set of \(n\) horses, all horses in \(H\) are the same color. Proof: We proceed by induction on \(n\). Basis: Suppose \(H\) is a set containing 1 horse. Clearly this horse is the same color as itself. Given a set of \(k+1\) horses \(H\) we can construct two sets of \(k\) horses. Suppose \(H=\left\\{h_{1}, h_{2}, h_{3}, \ldots h_{k+1}\right\\}\). Define \(H_{a}=\left\\{h_{1}, h_{2}, h_{3}, \ldots h_{k}\right\\}\) (i.e. \(H_{a}\) contains just the first \(k\) horses ) and \(H_{b}=\left\\{h_{2}, h_{3}, h_{4}, \ldots h_{k+1}\right\\}\) (i.e. \(H_{b}\) contains the last \(k\) horses). By the inductive hypothesis both these sets contain horses that are "all the same color." Also, all the horses from \(h_{2}\) to \(h_{k}\) are in both sets so both \(H_{a}\) and \(H_{b}\) con- tain only horses of this (same) color. Finally, we conclude that all the horses in \(H\) are the same color.

The Fibonacci numbers are a sequence of integers defined by the rule that a number in the sequence is the sum of the two that precede it. $$ F_{n+2}=F_{n}+F_{n+1} $$ The first two Fibonacci numbers (actually the zeroth and the first) are both 1 . Thus, the first several Fibonacci numbers are $$ F_{0}=1, F_{1}=1, F_{2}=2, F_{3}=3, F_{4}=5, F_{5}=8, F_{6}=13, F_{7}=21, \text { et cetera } $$ Use mathematical induction to prove the following formula involving Fibonacci numbers. $$ \sum_{i=0}^{n}\left(F_{i}\right)^{2}=F_{n} \cdot F_{n+1} $$