چنانچه محفل ریاضی را سودمند یافتید، لطفا برای حمایت از ما به کانال تلگرامی محفل ریاضی بپیوندید!
به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+3 امتیاز
74 بازدید
سوال شده در دبیرستان توسط Taha1381

اگر $f_n$ برابر تعداد کلمات متشکل از $a,b,c$ به طول $n$ باشد که از هر سه حرف متوالی حداقل دو تا یکسانند رابطه بازگشتی برای $f_n$ بیابید

1 پاسخ

+3 امتیاز
پاسخ داده شده توسط amirabbas
انتخاب شده توسط Taha1381
 
بهترین پاسخ

به محاسبه $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$

لطفا ما را در شبکه های اجتماعی دنبال کنید:
به محفل ریاضی ایرانیان خوش آمدید!
امروز : تاریخ شمسی اینجا نمایش داده می‌شود

♥ حمایت مالی

راهنمایی:

  • برای رفتن به سطر بعدی دو بار Enter بزنید.
  •  یک بار Enter یک فاصله محسوب می‌شود.
  •  _ایتالیک_ یا I و **پررنگ** یا B
  •  نقل‌قول با قراردادن > در ابتدای خط یا ❝
  • برای چپ به راست کردن متن کلیدهای Ctrl+Shift سمت چپ کیبورد را فشار دهید
  •  برای تایپ فرمول ابتدا روی ریاضی کلیک کرده و سپس به کمک آیکون‌های موجود فرمول را در بین دو علامت دلار

<math> $ $ </math>

بنویسید.

  •  برای اینکه فرمول در خط بعدی و وسط صفحه قرار گیرد دو علامت دلار اضافی بنویسید

<math> $$ $$ </math>


☑ راهنمایی بیشتر: راهنمای تایپ
71 نفر آنلاین
0 عضو و 71 مهمان در سایت حاضرند
بازدید امروز: 5796
بازدید دیروز: 8256
بازدید کل: 4500916
...