Let's start with n=0. The no of ways to climb is just one (be there where you are!). (2nd term of series)
n=1. No. of ways to climb is 1. (3rd term of series). (Obvious!)
Let's assume the no of ways for to climb p steps be x and climbing p+1 steps be y. We find for n=p+2.
Now, no of ways to climb (p+2) steps
= no of ways to climb p steps ( -> climbing 2 steps after climbing p steps)
+ no of ways to climb (p+1) steps ( -> climbing 1 step after climbing p+1 steps)
= x + y.
which is in the form of fibonacci series.
Hence proved.
Note : After climbing p steps, we can also climb 2 steps as (1+1) but these cases will be considered when we consider the case of climbing (p+1) steps and a single step.
~Vishal
On 1/23/06, Karthik K <[EMAIL PROTECTED]> wrote:
Hi,one of the questions in the code4bill is as follows...A person has to climb 22 steps.. at each point he has two choices... he can either choose to climb one step ahead or two steps ahead... you have to tell the total possible ways of climbing the steps... The problem becomes more interesting if we let the steps to be n...When i generated solution for n using a recursive approach.. it so happens that the possible combinations for n steps is the (n+2)nd fibonacci no if we assume fibonacci starts as 0,1,1,2,3,5,8...Can any one help me proving this pattern ??-Karthik
--
Vishal Padwal
Tel : 631-645-1406
