Summary: This paper shows how education-oriented spreadsheet-based explorations with Fibonacci numbers can result in the discovery of cycles of different periods formed by the orbits of a two-parametric difference equation of the second order. This equation is motivated through the introduction of the so-called Fibonacci sieve. The occurrence of the cycles is interpreted in terms of Fibonacci-like polynomials brought into being in the context of these explorations. This new class of polynomials possesses a number of interesting properties connected to the notion of a generalized golden ratio and can be used as a background for a spreadsheet-enhanced teaching of combinatorial identities and their formal demonstration. The paper reflects on activities designed for a technology-rich mathematics education course for prospective teachers of secondary mathematics. It is argued that an appropriate experience with a mathematical frontier can motivate the teachers to teach through a guided discovery mode.