document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=62971>Question 62971</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Richard Stanley writes in his book \"Enumerative Combinatorics\" that it is easily seen why <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=f%28n%29+=+f%28n-1%29%2Bf%28n-2%29 ALIGN=MIDDLE  ALT=\"f%28n%29+=+f%28n-1%29%2Bf%28n-2%29\"   DISABLED_style= \"max-width:90%; height:auto;\" > where f(n) is the number of subsets of [n] (<i>{1,2,3,..,n}</i>) that do not contain two consecutive integers.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Can someone actually explain why it is so, please?\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Thanks! </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #43945 by </B><A HREF=/tutors/aboutme.mpl?userid=joyofmath><B>joyofmath(189)</B></A><img src=\"/images/stars/stars-09.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=joyofmath><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/images/nopicture.jpg><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=43945\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> <b>Richard Stanley writes in his book \"Enumerative Combinatorics\" that it is easily seen why <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=f%28n%29+=+f%28n-1%29%2Bf%28n-2%29 ALIGN=MIDDLE  ALT=\"f%28n%29+=+f%28n-1%29%2Bf%28n-2%29\"   DISABLED_style= \"max-width:90%; height:auto;\" > where f(n) is the number of subsets of [n] (<i>{1,2,3,..,n}</i>) that do not contain two consecutive integers.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Can someone actually explain why it is so, please?</b>\r<BR>\n" );
document.write( "\n" );
document.write( "This is an interesting problem that took me a while to figure out. I can give you the gist of what's going on but you'd have to do a proof, either by induction or by contradiction to really prove the relationship.\r<BR>\n" );
document.write( "\n" );
document.write( "Here's the idea:\r<BR>\n" );
document.write( "\n" );
document.write( "Let's enumerate the subsets when n=3: {}{1}{2}{3}{13}<BR>\n" );
document.write( "Let's enumerate the subsets when n=4: {}{1}{2}{3}{4}{13}{14}{24}\r<BR>\n" );
document.write( "\n" );
document.write( "Now, let's say we want to construct the subsets when n=5. We can do this as follows, in two steps:\r<BR>\n" );
document.write( "\n" );
document.write( "1. Take all the subsets we used for n=4. They're all still legal when n=5.<BR>\n" );
document.write( "2. Take all the subsets we used for n=3. Add the number 5 to the end of each subset. That would give us {5}{15}{25}{35}{135}.\r<BR>\n" );
document.write( "\n" );
document.write( "Combining the subsets from n=3 (with the 5 tacked onto the end of each subset) and n=4 gives us the subsets for n=5 which is the motivation behind <IMG STYLE=\"max-width:80%;\" SRC=/cgi-bin/plot-formula.mpl?expression=f%28n%29+=+f%28n-1%29%2Bf%28n-2%29 ALIGN=MIDDLE  ALT=\"f%28n%29+=+f%28n-1%29%2Bf%28n-2%29\"   DISABLED_style= \"max-width:90%; height:auto;\" >.\r<BR>\n" );
document.write( "\n" );
document.write( "Note that there's no duplication between the subsets in n=3 with the 5's tacked on and the subsets in n=4 because the subsets in n=4 can't have any 5's (because n=4). Note also that tacking 5 onto the subsets in n=3 is legal since the n=3 subsets all end in 3 or less and thus tacking on 5 doesn't violate the nonconsecutive number constraint.\r<BR>\n" );
document.write( "\n" );
document.write( "Does this make sense?\r<BR>\n" );
document.write( "\n" );
document.write( "Note, you'd have to do a real proof, in particular you'd need to prove that no subsets were missing when we construct f(n) from f(n-1) and f(n-2). </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );