Moram reći da je ovo jedan od najinteresantnijih zadataka koje sam video u skorije vreme. Svideo mi se.
Možemo uočiti to, da u nekom „smislenom“ proizvodu, za sve matrice koje nisu na prvoj poziciji važi:
- [inlmath]A[/inlmath] može doći jedino nakon [inlmath]C[/inlmath];
- [inlmath]B[/inlmath] može doći nakon [inlmath]A[/inlmath] ili nakon [inlmath]B[/inlmath];
- [inlmath]C[/inlmath] takođe može doći nakon [inlmath]A[/inlmath] ili nakon [inlmath]B[/inlmath].
Npr. za [inlmath]n=2[/inlmath], mogući smisleni proizvodi bi bili [inlmath]CA[/inlmath], [inlmath]AB[/inlmath], [inlmath]BB[/inlmath], [inlmath]AC[/inlmath] ili [inlmath]BC[/inlmath] (slučaj [inlmath]n=1[/inlmath] je trivijalan, za njega su mogućnosti, naravno – [inlmath]A[/inlmath], [inlmath]B[/inlmath] ili [inlmath]C[/inlmath]).
Označimo sa [inlmath]P_{A_k}[/inlmath] broj smislenih proizvoda za [inlmath]n=k[/inlmath] kod kojih je [inlmath]A[/inlmath] na poslednjem mestu.
Analogno, označimo sa [inlmath]P_{B_k}[/inlmath] broj smislenih proizvoda za [inlmath]n=k[/inlmath] kod kojih je [inlmath]B[/inlmath] na poslednjem mestu, a sa [inlmath]P_{C_k}[/inlmath] broj smislenih proizvoda za [inlmath]n=k[/inlmath] kod kojih je [inlmath]C[/inlmath] na poslednjem mestu.
I, neka je [inlmath]P_k=P_{A_k}+P_{B_k}+P_{C_k}[/inlmath] ukupan broj mogućih proizvoda za [inlmath]n=k[/inlmath] (npr. [inlmath]P_1=3[/inlmath], [inlmath]P_2=5[/inlmath], [inlmath]P_3=8[/inlmath] itd.)
Posmatrajmo sada slučaj dodavanja jedne matrice u proizvod, tj. povećanje [inlmath]n[/inlmath] sa [inlmath]k[/inlmath] na [inlmath]k+1[/inlmath]:
- Pošto [inlmath]A[/inlmath] može doći jedino nakon [inlmath]C[/inlmath], sledi da je [inlmath]P_{A_{k+1}}=P_{C_k}[/inlmath];
- Pošto [inlmath]B[/inlmath] može doći nakon [inlmath]A[/inlmath] ili nakon [inlmath]B[/inlmath], sledi da je [inlmath]P_{B_{k+1}}=P_{A_k}+P_{B_k}[/inlmath];
- Pošto [inlmath]C[/inlmath] može doći nakon [inlmath]A[/inlmath] ili nakon [inlmath]B[/inlmath], sledi da je [inlmath]P_{C_{k+1}}=P_{A_k}+P_{B_k}[/inlmath].
Isto tako je i:
- [inlmath]P_{A_{k+2}}=P_{C_{k+1}}[/inlmath];
- [inlmath]P_{B_{k+2}}=P_{A_{k+1}}+P_{B_{k+1}}[/inlmath];
- [inlmath]P_{C_{k+2}}=P_{A_{k+1}}+P_{B_{k+1}}[/inlmath].
Odatle sledi:
[dispmath]\begin{align}
P_{k+2}&=P_{A_{k+2}}+P_{B_{k+2}}+P_{C_{k+2}}\\
&=\underbrace{P_{C_{k+1}}+P_{A_{k+1}}+P_{B_{k+1}}}_{P_{k+1}}+P_{A_{k+1}}+P_{B_{k+1}}\\
&=P_{k+1}+\underbrace{P_{C_k}+P_{A_k}+P_{B_k}}_{P_k}\\
&=P_{k+1}+P_k
\end{align}[/dispmath] čime je pokazano da ovo jeste Fibonačijev niz.