(۰۵ اسفند ۱۳۹۵ ۰۹:۲۰ ب.ظ)msour44 نوشته شده توسط:  

(05 اسفند ۱۳۹۵ ۰۵:۱۰ ب.ظ)ss311 نوشته شده توسط:  یک دنباله به طول ۸،ساخته شده از نمادهای {۰و۱و...و۹} خوب نامیده میشود هرگاه شامل تعداد زوجی صفر باشد.تعداد دنباله های خوب به طول ۸ کدام است؟
۱)۸^۱۰
۲)۹^۱۰
۳)(۲/(۸^۸ -۸^۱۰))
۴) (۲/(۸^۸ +۸^۱۰))

برای حالت کلی دنباله های خوب به طول n
به کمک روابط بازگستی اگر تعداد دنباله های خوب به طول n را [tex]a_n[/tex] بنامیم رقم اول یا صفراست یا صفر نیست(۹ حالت دیگر)
اگر صفر نباشد مسئله کاهش یافته به طول n-1 داریم یعنی [tex]a_{n-1}[/tex]
اگر صفر باشد پس باید در n-1 مکان دیگر تعداد فرد صفر داشته باشیم که معادل تعداد کل حالت منهای تعداد دنباله های خوب به طول n-1
پس رابطه بازگشتی برابر با [tex]a_n=9a_{n-1}+10^{n-1}-a_{n-1}\: \: \: \Longrightarrow\: a_n=8a_{n-1}+10^{n-1}\: [/tex]
با [tex]a_0=1\: \: ,\: \: a_1=9[/tex] که بعد از حل داریم [tex]a_n=\frac{\: 1}{2}(8^n+10^n)[/tex]
حال کافیه به جای n مقدار ۸ قرار دهیم که گزینه ۴ حاصل می شود