{"id":290,"date":"2017-11-15T21:01:12","date_gmt":"2017-11-16T05:01:12","guid":{"rendered":"https:\/\/blogs.ubc.ca\/organizingchaos\/?p=290"},"modified":"2018-01-16T20:58:17","modified_gmt":"2018-01-17T04:58:17","slug":"mathematical-aside-golden-mean-shift-and-pascals-triangle-part-3","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/organizingchaos\/2017\/11\/15\/mathematical-aside-golden-mean-shift-and-pascals-triangle-part-3\/","title":{"rendered":"Mathematical Aside: Golden Mean Shift and Pascal\u2019s Triangle (Part 3)"},"content":{"rendered":"<p>As was derived in <a href=\"https:\/\/blogs.ubc.ca\/organizingchaos\/2017\/11\/15\/mathematical-aside-golden-mean-shift-and-pascals-triangle-part-2\/\">Part 2<\/a>, <img src='https:\/\/s0.wp.com\/latex.php?latex=%7Cc_%7Bm%2Cn%7D%7C%3D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='|c_{m,n}|=' title='|c_{m,n}|=' class='latex' \/> <img src='https:\/\/s0.wp.com\/latex.php?latex=%7Bn-%28m-1%29%7D%5Cchoose%7Bm%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='{n-(m-1)}\\choose{m}' title='{n-(m-1)}\\choose{m}' class='latex' \/> where <img src='https:\/\/s0.wp.com\/latex.php?latex=c_%7Bm%2Cn%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='c_{m,n}' title='c_{m,n}' class='latex' \/> denotes the set of binary strings of length <img src='https:\/\/s0.wp.com\/latex.php?latex=n&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='n' title='n' class='latex' \/> with exactly <img src='https:\/\/s0.wp.com\/latex.php?latex=m&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='m' title='m' class='latex' \/> non-adjacent ones.<\/p>\n<p>Today we will analyze\u00a0<img src='https:\/\/s0.wp.com\/latex.php?latex=c_%7Bn%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='c_{n}' title='c_{n}' class='latex' \/> the set of\u00a0binary strings of length <img src='https:\/\/s0.wp.com\/latex.php?latex=n&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='n' title='n' class='latex' \/> with any number of non-adjacent ones. We will need some additional notation.<\/p>\n<ul>\n<li><img src='https:\/\/s0.wp.com\/latex.php?latex=c_%7Bn%2C0%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='c_{n,0}' title='c_{n,0}' class='latex' \/> denote the the subset of\u00a0<img src='https:\/\/s0.wp.com\/latex.php?latex=c_%7Bn%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='c_{n}' title='c_{n}' class='latex' \/> ending with 0<\/li>\n<li><img src='https:\/\/s0.wp.com\/latex.php?latex=c_%7Bn%2C1%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='c_{n,1}' title='c_{n,1}' class='latex' \/> denote the the subset of\u00a0<img src='https:\/\/s0.wp.com\/latex.php?latex=c_%7Bn%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='c_{n}' title='c_{n}' class='latex' \/> ending with 1<\/li>\n<\/ul>\n<p>After some thought, we realize that\u00a0<img src='https:\/\/s0.wp.com\/latex.php?latex=c_%7Bn%2C0%7D+%3Dc_%7Bn-1%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='c_{n,0} =c_{n-1}' title='c_{n,0} =c_{n-1}' class='latex' \/> and\u00a0<img src='https:\/\/s0.wp.com\/latex.php?latex=c_%7Bn-2%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='c_{n-2}' title='c_{n-2}' class='latex' \/>. We can then derive the recurrence\u00a0<img src='https:\/\/s0.wp.com\/latex.php?latex=%7Cc_%7Bn%7D%7C+%3D+%7Cc_%7Bn%2C0%7D%7C%2B%7Cc_%7Bn%2C1%7D%7C%3D%7Cc_%7Bn-1%7D%7C%2B%7Cc_%7Bn-2%7D%7C&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='|c_{n}| = |c_{n,0}|+|c_{n,1}|=|c_{n-1}|+|c_{n-2}|' title='|c_{n}| = |c_{n,0}|+|c_{n,1}|=|c_{n-1}|+|c_{n-2}|' class='latex' \/>. After verifying the base case, we can conclude <img src='https:\/\/s0.wp.com\/latex.php?latex=%7Cc_%7Bn%7D%7C+%3D+F_%7Bn%2B2%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='|c_{n}| = F_{n+2}' title='|c_{n}| = F_{n+2}' class='latex' \/>, the Fibonacci Numbers!<\/p>\n<p>Another way to compute <img src='https:\/\/s0.wp.com\/latex.php?latex=%7Cc_%7Bn%7D%7C&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='|c_{n}|' title='|c_{n}|' class='latex' \/> is\u00a0<img src='https:\/\/s0.wp.com\/latex.php?latex=%7Cc_%7Bn%7D%7C+%3D+%5Csum_%7Bm%3D0%7D%5E%7B%5Cinfty%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='|c_{n}| = \\sum_{m=0}^{\\infty}' title='|c_{n}| = \\sum_{m=0}^{\\infty}' class='latex' \/> <img src='https:\/\/s0.wp.com\/latex.php?latex=%7Bn-%28m-1%29%7D%5Cchoose%7Bm%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='{n-(m-1)}\\choose{m}' title='{n-(m-1)}\\choose{m}' class='latex' \/>.<\/p>\n<p>Therefore <img src='https:\/\/s0.wp.com\/latex.php?latex=F_%7Bn%2B2%7D+%3D+&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='F_{n+2} = ' title='F_{n+2} = ' class='latex' \/> <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Csum_%7Bm%3D0%7D%5E%7B%5Cinfty%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\sum_{m=0}^{\\infty}' title='\\sum_{m=0}^{\\infty}' class='latex' \/> <img src='https:\/\/s0.wp.com\/latex.php?latex=%7Bn-%28m-1%29%7D%5Cchoose%7Bm%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='{n-(m-1)}\\choose{m}' title='{n-(m-1)}\\choose{m}' class='latex' \/>.<\/p>\n<p>With some shifting, we can solve for the <img src='https:\/\/s0.wp.com\/latex.php?latex=n%5E%7Bth%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='n^{th}' title='n^{th}' class='latex' \/> Fibonnaci number :<\/p>\n<p><img src='https:\/\/s0.wp.com\/latex.php?latex=F_%7Bn%7D+%3D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='F_{n} =' title='F_{n} =' class='latex' \/> <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Csum_%7Bm%3D0%7D%5E%7B%5Cinfty%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\sum_{m=0}^{\\infty}' title='\\sum_{m=0}^{\\infty}' class='latex' \/> <img src='https:\/\/s0.wp.com\/latex.php?latex=%7Bn-m-1%7D%5Cchoose%7Bm%7D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='{n-m-1}\\choose{m}' title='{n-m-1}\\choose{m}' class='latex' \/><\/p>\n<p>While this formula can be quite easily verified inductively, its nice to construct it explicitly.<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>As was derived in Part 2, where denotes the set of binary strings of length with exactly non-adjacent ones. Today we will analyze\u00a0 the set of\u00a0binary strings of length with any number of non-adjacent ones. We will need some additional notation. denote the the subset of\u00a0 ending with 0 denote the the subset of\u00a0 ending [&hellip;]<\/p>\n","protected":false},"author":28516,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13426,1],"tags":[],"class_list":["post-290","post","type-post","status-publish","format-standard","hentry","category-asides","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/posts\/290","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/users\/28516"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/comments?post=290"}],"version-history":[{"count":20,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/posts\/290\/revisions"}],"predecessor-version":[{"id":343,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/posts\/290\/revisions\/343"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/media?parent=290"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/categories?post=290"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/tags?post=290"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}