  A permutation $\pi \in S_n$ is said to {\it avoid} a permutation $\sigma \in
S_k$ whenever $\pi$ contains no subsequence with all of the same pairwise
comparisons as $\sigma$. For any set $R$ of permutations, we write $S_n(R)$ to
denote the set of permutations in $S_n$ which avoid every permutation in $R$.
In 1985 Simion and Schmidt showed that $|S_n(132, 213, 123)|$ is equal to the
Fibonacci number $F_{n+1}$. In this paper we generalize this result in several
ways. We first use a result of Mansour to show that for any permutation $\tau$
in a certain infinite family of permutations, $|S_n(132, 213, \tau)|$ is given
in terms of Fibonacci numbers or $k$-generalized Fibonacci numbers. In many
cases we give explicit enumerations, which we prove bijectively. We then use
generating function techniques to show that for any permutation $\gamma$ in a
second infinite family of permutations, $|S_n(123, 132, \gamma)|$ is also given
in terms of Fibonacci numbers or $k$-generalized Fibonacci numbers. In many
cases we give explicit enumerations, some of which we prove bijectively. We go
on to use generating function techniques to show that for any permutation
$\omega$ in a third infinite family of permutations, $|S_n(132, 2341, \omega)|$
is given in terms of Fibonacci numbers, and for any permutation $\mu$ in a
fourth infinite family of permutations, $|S_n(132, 3241, \mu)|$ is given in
terms of Fibonacci numbers and $k$-generalized Fibonacci numbers. In several
cases we give explicit enumerations. We conclude by giving an infinite class of
examples of a set $R$ of permutations for which $|S_n(R)|$ satisfies a linear
homogeneous recurrence relation with constant coefficients.
