How many ways can you ascend a stairway of any number of steps?

Question

I wrote out by hand every way from 1 to 6 steps and came up with the formula $f(x) = 2^{x-2}$. Is that correct? I then tried to solve the problem recursively but could not. So I wanted to know if my initial function was incorrect, or if i'm just too daft to find a recursive solution to this.

Answer 1

You want all ways to get $6$ steps.

Mathematically we can see this as a composition of the number $6$:

$1+1+1+1+1+1$

$1+1+1+1+2$

$(\ldots)$

$6$

The number of compositions of $x$ is given by $2^{x-1}$. See the Wikipedia article for a short proof.

Answer 2

Apparenly you want to move only up and forbid steps of size $0$ (naturally, as otherwise there are infinitely many solutions), and use of the first and last steps of the $n$ steps are obligatory. Then any solution is given by the subset of the remaining steps that are used, which indeed gives $2^{n-2}$ ways.

Answer 3

See here if I am no wrong then you are asking for : How many ways are there to break a number(integer) into several parts. such as: 3= 1+1+1 OR 1+2 OR 2+1 OR 3 So there is 4 ways to express 3 in such manner..ok.. if you have your question something like: if the number is 'n' then what would be the answer?....the you can have a look onto my question.....here we will map our problem into a similar problem which is easier to compute and very easy to follow....So here we go!!

Let us consider that we have a number 4(that is our n=4) now the question is how many ways are there to express 4 as we have done earlier for 3.

See here: Let us now wriite 4 as four sticks ok.....so now we have : { | | | | } ok ...so we have 4 sticks in our hand.

Now see,we can easily observe that : There are 3 spaces between 4 sticks and there are there 3 places to put '+' SIGN or a 'comma' SIGN (' , ') into these 3 places between these 4 sticks.ok...got it....

Now see,If we are interested to calculate the number of ways to express this number(n=4) like this special manner as done for 3 earlier , you can easily say that the number of possible ways is nothing but HOW MANY WAYS ARE THERE TO PUT A ' + ' SIGN OR A 'COMMA' SIGN IN THESE 3 places....

Because, See here if we have an arrangement like this: { | + | , | , | } ------(Here we have expressed the number 4 as: 2 1 1, It has a sum of 4) Now if we have an arrangement like this: { | , |+| + | }------------(Here we have expressed the number n=4 as: 1 3, It has a sum of 4)

      So you can see that the number of possible arrangements is nothing but : in how many ways we can place + sign and comma sign mutually inbetween the gaps between the sticks that helps us to compute the number of ways to break any number n.

So, we have the case for n=4 is: 2^(4-1) = 2^3 = 8.Because we have 3 places between 4 sticks.So the places admissible for the signs arre only 3 for the 4 sticks OR there are only 3 gaps where we can put the + or COMMA sign.

Now if we have the nummber 'n' in general we will have: { | | | | - - - | } .....(there are 'n' number of sticks and we have (n - 1) number of gaps between them where we can put the + OR the COMMA sign.)

Then, we can infer that we have total of : 2^(n -1) possible ways to break a number 'n' having highest length equals to 'n' because you can see that the number 4 can be written as : 4 itself,it is also a way to express this number.

but ingeneral we have found the closed formula for 'n' and it is: [ 2^( n - 1) ]

Hope this above discussion will help you a bit.Best of luck.