Kādas valodas alfabētā ir \(i\) patskaņi (\(i \geq 2\)) un \(j\) līdzskaņi (\(j \geq 2\)). Šajā valodā par vārdu sauc jebkuru galīgu burtu (patskaņu un līdzskaņu) virkni, kas satur vismaz vienu burtu un kurā nekādi divi patskaņi neparādās pēc kārtas un pēc kārtas uzrakstīti līdzskaņi ir ne vairāk kā divi (piemēram, ja " \(A\) " ir patskanis, bet " \(B\) " līdzskanis, tad, piemēram, " \(ABBA\) " ir vārds, turpretī " \(BAAB\) " un " \(ABBBA\) " nav vārdi).
Ar \(S(n)\) apzīmēsim visu to vārdu skaitu, kuri sastāv no \(n\) burtiem, \(n \geq 1\).
Pierādīt, ka visiem naturāliem skaitļiem \(n\) ir spēkā vienādība
\[S(n+3)=i \cdot j \cdot S(n+1)+i \cdot j^{2} \cdot S(n)\]
Ar \(a(n)\) apzīmēsim \(n\) burtus garo vārdu, kas sākas ar patskani, skaitu, bet ar \(b(n)-n\) burtus garo vārdu, kas sākas ar līdzskani, skaitu. Tad \(S(n)=a(n)+b(n)\).
Ja vārds sākas ar patskani, tad nākamais burts var būt tikai līdzskanis (jo divi patskaņi nevar būt blakus), tāpēc \(a(n)=i \cdot b(n-1)\).
Ja vārds sākas ar līdzskani, tad nākamais burts var būt vai nu patskanis, vai arī vēl viens līdzskanis, bet tad trešais burts noteikti ir patskanis (jo blakus var būt ne vairāk kā divi līdzskaņi), tāpēc \(b(n)=j \cdot a(n-1)+j^{2} \cdot a(n-2)\).
Tātad \(S(n)=a(n)+b(n)=i \cdot b(n-1)+j \cdot a(n-1)+j^{2} \cdot a(n-2)=\)
\(=i \cdot\left(j \cdot a(n-2)+j^{2} \cdot a(n-3)\right)+j \cdot(i \cdot b(n-2))+j^{2} \cdot(i \cdot b(n-3))=\)
\(=i \cdot j \cdot(a(n-2)+b(n-2))+i \cdot j^{2} \cdot\left.(a(n-3)+b(n-3)=i \cdot j \cdot S(n-2)+i \cdot j^{2} \cdot S(n-3) \quad\right.\)
jeb
\(S(n+3)=i \cdot j \cdot S(n+1)+i \cdot j^{2} \cdot S(n)\), k.b.j.