Cik veidos rindā var iestādīt septiņus kokus - liepas, ozolus, priedes un egles - tā, lai nekur blakus neatrastos divi skuju koki? (Nav obligāti jāizmanto visas koku sugas. Veidi, kas atšķiras ar koku secību rindā, ir dažādi.)
Ar \(k_{n}\) apzīmējam dažādo veidu skaitu, kā rindā iestādīt \(n\) kokus atbilstoši uzdevuma nosacījumiem. Ja pirmais ir lapu koks (\(2\) veidi), tad pārējos \(n-1\) kokus var iestādīt \(k_{n-1}\) veidos.
Ja pirmais ir skuju koks (\(2\) veidi), tad otrajam jābūt lapu kokam (\(2\) veidi), bet pārējos \(n-2\) kokus var iestādīt \(k_{n-2}\) veidos.
Tātad \(n\) kokus rindā, atbilstoši uzdevuma nosacījumiem, var iestādīt
\[k_{n}=2 \cdot k_{n-1}+2 \cdot 2 \cdot k_{n-2}=2k_{n-1}+4k_{n-2}\]
Veidos. Tā kā \(k_{1}=4\) (liepa, ozols, priede, egle) un \(k_{2}=2 \cdot 4+2 \cdot 2=12\) (tas ir, ja pirmais ir lapu koks (\(2\) veidi), tad otrais var būt jebkurš no pārējiem četriem kokiem, ja pirmais ir skuju koks (\(2\) veidi), tad otrais var būt jebkurš no pārējiem diviem lapu kokiem). Tālāk, izmantojot iegūto formulu \(k_{n}=2k_{n-1}+4k_{n-2}\), iegūstam, ka pavisam ir \(4352\) dažādi veidi, kā rindā iestādīt septiņus kokus, kas apmierina uzdevuma nosacījumus. | \(n\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | \(k_{n}\) | \(4\) | \(12\) | \(40\) | \(128\) | \(416\) | \(1344\) | \(4352\) |