document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=36496>Question 36496</A>: <I><SPAN STYLE=\"word-break: break-all;\"> In how many ways can you walk up a stairway that has 7 steps if you can take 1 0r 2 steps at a time? </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #22421 by </B><A HREF=/tutors/aboutme.mpl?userid=kev82><B>kev82(151)</B></A><img src=\"/images/stars/stars-09.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=kev82><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=22421\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> Hi,\r<BR>\n" );
document.write( "\n" );
document.write( "Are you familiar with reccurence relations? Hopefully you are because I don't know how to attempt this otherwise.\r<BR>\n" );
document.write( "\n" );
document.write( "let N(x) be the number of ways to get up x stairs, where you can either take one or two steps at a time. Obviously N(1)=1 because when you have one stair left all you can do is walk up it.\r<BR>\n" );
document.write( "\n" );
document.write( "With two stairs left to go, we can go up both stairs at once or we can go up one stair and be on stair 1. So N(2)=1+N(1)=1+1=2.\r<BR>\n" );
document.write( "\n" );
document.write( "If there are x stairs left, then we can either go up one stair and be on stair x-1 or we can go up two stairs and be on stair x-2. So N(x)=N(x-1)+N(x-2). We want to know N(7), lets work it out.\r<BR>\n" );
document.write( "\n" );
document.write( "N(1)=1<BR>\n" );
document.write( "N(2)=N(1)+1=1+1=2<BR>\n" );
document.write( "N(3)=N(2)+N(1)=2+1=3<BR>\n" );
document.write( "N(4)=N(3)+N(2)=3+2=5<BR>\n" );
document.write( "N(5)=N(4)+N(3)=5+3=8<BR>\n" );
document.write( "N(6)=N(5)+N(4)=8+5=13<BR>\n" );
document.write( "N(7)=N(6)+N(5)=13+8=21\r<BR>\n" );
document.write( "\n" );
document.write( "So there's your answer, 21. Hopefully you should recognise this as the Fibbionacci sequence.\r<BR>\n" );
document.write( "\n" );
document.write( "Hope that helps,<BR>\n" );
document.write( "Kev </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );