به محاسبه $f_n$ می پردازیم. در $f_n$ یک جایگاه به جایگاه های $f_{n-1}$ اضافه می شود که سه انتخاب در آن داریم پس تعداد کل حالت ها برابر با $3f_{n-1}$ است.اما برخی از این حالت ها مورد قبول ما نخواهد بود این حالت ها را محاسبه می کنیم. حالتی که دو حرف پایانی $f_{n-1}$ یکسان باشد مستقل از حرفی که در جایگاه جدید قرار می دهیم مورد قبول ما است. پس حالتی مشکل ساز است که دو حرف پایانی $f_{n-1}$ متفاوت باشند. اگر دو حرف پایانی متفاوت باشند به ازای یک انتخاب در جایگاه جدید به حالتی نامطلوب خواهیم رسید. با در نظر گرفتن این تناظر می توان گفت تعداد حالاتی که باید از $3f_{n-1}$ کم کنیم با تعداد $f_{n-1}$ هایی که دو حرف پایانی آن ها متفاوت است برابر است.که برای محاسبه اینها هم می توان تعداد حالاتی از $f_{n-1}$ که دو حرف پایانی آن ها یکسان است را از کل $f_{n-1}$ کم کرد. اگر به $f_{n-2}$ جایگاهی جدید اضافه کنیم به ازای یک حالت در این جایگاه جدید دو حرف پایانی $f_{n-1}$ یکسان می شود. بنابراین:
$$ f_n = 3f_{n-1}-(f_{n-1} - f_{n-2}) = 2f_{n-1} + f_{n-2} $$
همچنین می دانیم $f_1 = 3$ و $f_2 = 9$
