91Ó°ÊÓ

Let \(f_{0}, f_{1}, f_{2}, \ldots, f_{n}, \ldots\) denote the Fibonacci sequence. By evaluating each of the following expressions for small values of \(n\), conjecture a general formula and then prove it, using mathematical induction and the Fibonacci recurrence: (a) \(f_{1}+f_{3}+\cdots+f_{2 n-1}\) (b) \(f_{0}+f_{2}+\cdots+f_{2 n}\) (c) \(f_{0}-f_{1}+f_{2}-\cdots+(-1)^{n} f_{n}\) (d) \(f_{0}^{2}+f_{1}^{2}+\cdots+f_{n}^{2}\)

Prove the following about the Fibonacci numbers: (a) \(f_{n}\) is even if and only if \(n\) is divisible by 3 . (b) \(f_{n}\) is divisible by 3 if and only if \(n\) is divisible by 4 . (c) \(f_{n}\) is divisible by 4 if and only if \(n\) is divisible by 6 .

Consider a 1-by-n chessboard. Suppose we color each square of the chessboard with one of the two colors red and blue. Let \(h_{n}\) be the number of colorings in which no two squares that are colored red are adjacent. Find and verify a recurrence relation that \(h_{n}\) satisfies. Then derive a formula for \(h_{n}\).

The Lucas numbers \(l_{0}, l_{1}, l_{2}, \ldots, l_{n} \ldots\) are defined using the same recurrence relation defining the Fibonacci numbers, but with different initial conditions: $$L_{n}=l_{n-1}+l_{n-2},(n \geq 2), l_{0}=2, l_{1}=1$$ Prove that (a) \(l_{n}=f_{n-1}+f_{n+1}\) for \(n \geq 1\) (b) \(l_{0}^{2}+l_{1}^{2}+\cdots+l_{n}^{2}=l_{n} l_{n+1}+2\) for \(n \geq 0\)

Determine the generating function for each of the following sequences: (a) \(c^{0}=1, c, c^{2}, \ldots, c^{n}, \ldots\) (b) \(1,-1,1,-1, \ldots,(-1)^{n}, \ldots\) (c) \(\left(\begin{array}{l}\alpha \\\ 0\end{array}\right),-\left(\begin{array}{c}\alpha \\\ 1\end{array}\right),\left(\begin{array}{c}\alpha \\ 2\end{array}\right), \ldots,(-1)^{n}\left(\begin{array}{c}\alpha \\ n\end{array}\right), \ldots,(\alpha\) is a real number \()\) (d) \(1, \frac{1}{1}, \frac{1}{2}, \ldots, \frac{1}{n}, \ldots\) (e) \(1,-\frac{1}{11}, \frac{1}{21}, \ldots,(-1)^{n} \frac{1}{n}, \ldots\)

Let \(S\) be the multiset \(\left\\{\infty \cdot e_{1}, \infty \cdot e_{2}, \infty \cdot e_{3}, \infty \cdot e_{4}\right\\}\). Determine the generating function for the sequence \(h_{0}, h_{1}, h_{2}, \ldots, h_{n}, \ldots\), where \(h_{n}\) is the number of \(n\) combinations of \(S\) with the following added restrictions: (a) Each \(e_{i}\) occurs an odd number of times. (b) Each \(e_{i}\) occurs a multiple-of-3 number of times. (c) The element \(e_{1}\) does not occur, and \(e_{2}\) occurs at most once. (d) The element \(e_{1}\) occurs 1,3, or 11 times, and the element \(e_{2}\) occurs 2,4, or 5 times. (e) Each \(e_{i}\) occurs at least 10 times.

Determine the generating function for the sequence of cubes $$0,1,8, \ldots, n^{3}, \ldots$$

Formulate a combinatorial problem for which the generating function is $$\left(1+x+x^{2}\right)\left(1+x^{2}+x^{4}+x^{6}\right)\left(1+x^{2}+x^{4}+\cdots\right)\left(x+x^{2}+x^{3}+\cdots\right)$$

Let \(h_{0}, h_{1}, h_{2}, \ldots, h_{n}, \ldots\) be the sequence defined by \(h_{n}=\left(\begin{array}{c}n \\ 2\end{array}\right),(n \geq 0)\). Deter- mine the generating function for the sequence.

Let \(h_{0}, h_{1}, h_{2}, \ldots, h_{n}, \ldots\) be the sequence defined by \(h_{n}=\left(\begin{array}{c}n \\ 3\end{array}\right),(n \geq 0)\). Deter- mine the generating function for the sequence.