سلام. وقت بخیر.
یه رابطه بازگشتی نیازه. تعداد رشته‌های n بیتی که ۰۰ ندارن رو $a_n$ اگه قرار باشه رشته شامل ۰۰ نباشه، سمت راست رشته یکی از دو حالت زیر رو داره:
$1$ : در این حالت در سمت چپ این رقم، یه رشته n-1 بیتی بدون ۰۰ بیاد. تعداد این رشته‌ها هست $a_{n-1}$.
$0$ : در این حالت در سمت چپ این رقم، حتماً یه $1$ بیاد و سمت چپ اون، یه رشته n-2 بیتی بدون ۰۰ بیاد. تعداد این رشته‌ها هست $a_{n-2}$.
تعداد رشته‌های ۱ بیتی و ۲ بیتی بدون ۰۰ هم به ترتیب ۲ و ۳ هست. میتونید به صورت بازگشتی این مقدار رو برای هر n حساب کنید یا رابطه بازگشتی رو برای رسیدن به رابطه صریح حل کنید.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


احساس میکنم با خوندن این مطالب راحت به جواب میرسی و خودت میرسی


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


ببین این همین رشته همینگ هست که شما دنبالش هستی، منتهی یه شرط داره و اون اینه که دو صفر متوالی نداشته باشه و باید از روشی که تو لینک دوم فرستادم بری جلو، این جمله رو خوندم تو یکی از این لینکها که برات فرستادم:

رشته بیتی با طول n شامل دقیقاً r+1 بیت یک وجود دارد. (توجه کنید که آخرین جمله اثبات، با تغییر مغیر j=k-1 نتیجه می‌شود. (

چون سمت چپ و راست هر دو اشیاء یکسانی را می‌شمارند، با هم برابرند.