{"id":5013,"date":"2025-04-29T15:59:50","date_gmt":"2025-04-29T19:59:50","guid":{"rendered":"http:\/\/mathfun4kids.com\/mlog\/?p=5013"},"modified":"2025-05-02T10:25:43","modified_gmt":"2025-05-02T14:25:43","slug":"combination-challenge-2025-04-29","status":"publish","type":"post","link":"https:\/\/mathfun4kids.com\/mlog\/?p=5013","title":{"rendered":"Combination Challenge – 2025\/04\/29"},"content":{"rendered":"\n

Let $f(n)$ be the number of binary strings with length as $n$ that they do not contain a sub-string as “$010$” nor “$101$”. Prove that for $n\\ge 3$: $f(n)=f(n-1)+f(n-2)$ \ud83d\udd11<\/a><\/p>\n\n\n\n

\n\n\n\n

Proof:<\/strong> For $n=1$, we have $2$ possible binary strings, as $0$, and $1$. We have $f(1)=2$ as none of the $2$ possible binary strings containing $010$ or $101$.<\/p>\n\n\n\n

For $n=2$, we have $4$ possible binary strings, as $00$, $01$, $10$, and $11$. We have $f(2)=4$ as none of the $4$ possible binary strings containing $010$ or $101$.<\/p>\n\n\n\n

When $n=3$, there are $8$ possible binary strings, as $000$, $001$, $010$, $011$, $100$, $101$, $110$, and $111$. Excluding $010$ and $101$, we have $f(3)=6$.<\/p>\n\n\n\n

Therefore, $f(n)=f(n-1)+f(n-2)$ when $n=3$.<\/p>\n\n\n\n

For a binary string of length $n$ that does not contain a sub-string as $010$ nor $101$, the string can end up with a suffix as $00$, $01$, $10$, or $11$. Let $a(n)$, $b(n)$, $c(n)$, and $d(n)$ be the number of strings with length as $n$ that end up with a suffix as $00$, $01$, $10$, and $11$ respectively. Therefore $$f(n)=a(n)+b(n)+c(n)+d(n)$$ Additionally, we have the following relationships:<\/p>\n\n\n\n$$\n\\begin{array}{rcl}\na(n)&=&a(n-1)+c(n-1)\\\\\nb(n)&=&a(n-1)\\\\\nc(n)&=&d(n-1)\\\\\nd(n)&=&b(n-1)+d(n-1)\\\\\n\\end{array}\n$$\n\n\n\n

Therefore<\/p>\n\n\n\n$$\n\\begin{array}{rcl}\nf(n)&=&a(n)+b(n)+c(n)+d(n)\\\\\n\\ &=&(a(n-1)+c(n-1))+a(n-1)+d(n-1)+(b(n-1)+d(n-1))\\\\\n\\ &=&(a(n-1)+b(n-1)+c(n-1)+d(n-1))+(a(n-1)+d(n-1))\\\\\n\\ &=&f(n-1)+((a(n-2)+c(n-2))+(b(n-2)+d(n-2)))\\\\\n\\ &=&f(n-1)+(a(n-2)+b(n-2)+c(n-2)+d(n-2))\\\\\n\\ &=&f(n-1)+f(n-2)\\\\\n\\end{array}\n$$\n\n\n\n

Combining with the case when $n=3$, it is proved that $\\boxed{f(n)=f(n-1)+f(n-2)}$.<\/p>\n\n\n\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Let $f(n)$ be the number of binary strings with length as $n$ that they do not contain a sub-string as “$010$” nor “$101$”. Prove that for $n\\ge 3$: $f(n)=f(n-1)+f(n-2)$ \ud83d\udd11 Proof: For $n=1$, we have $2$ possible binary strings, as … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false},"categories":[10],"tags":[],"_links":{"self":[{"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/posts\/5013"}],"collection":[{"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5013"}],"version-history":[{"count":34,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/posts\/5013\/revisions"}],"predecessor-version":[{"id":5109,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/posts\/5013\/revisions\/5109"}],"wp:attachment":[{"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5013"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5013"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5013"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}