Conference rusure::math

The walker can reach the Kth step either by skipping from the K-2th step
or by stepping from the K-1th, so the number of ways to reach the Kth step
is the sum of the ways to reach the other two, i.e. the Kth Fibonnaci number.

Lynn Yarbrough

Suppose there are n steps.  Let f(x) denote the number of ways in which x
steps can be climbed.  Then the person may take either one step or two
together.  If one step is taken, there are f(n-1) ways to take the remaining
steps.  If two steps are taken, there are f(n-2) ways to take the remaining
steps.  Thus, f(n) = f(n-1)+f(n-2).  Clearly, there is only one way to climb
zero steps or one step, so f(0) = f(1) = 1.

So f(100) is the hundredth Fibonacci number, which is about 5.731478 * 10^20.


				-- edp

	I don't see that the way to climb zero steps is "clearly"
anything but undefined or arguable; however, clearly f(2) = 2.

-cjc

Re .3:

Suppose you are zero steps away from your goal?  How many choices do you have
about what to do next?  One:  Do nothing.

Or, consider the number of ways to climb two steps.  This can be solved by the
sequence 1, 1 or by the sequence 2.  Climbing zero steps can be solved by the
empty sequence.  No other sequence works.


				-- edp

Re .4:

>Suppose you are zero steps away from your goal?  How many choices do you have
>about what to do next?  One:  Do nothing.

>Climbing zero steps can be solved by the empty sequence.
>No other sequence works.

Since climbing zero steps is outside the range of the stated problem, there
are an infinite number of sequences, e. g. take a taxi. My point is that,
given the stated problem, f(n) is defined only for 0 <  n < 101. Therefore, the
induction should properly begin with 1, not 0.

>Or, consider the number of ways to climb two steps.  This can be solved by the
>sequence 1, 1 or by the sequence 2.

    That's what I said: "Clearly f(2) = 2."

-cjc-

Re .5:

>> Climbing zero steps can be solved by the empty sequence.
>> No other sequence works.

> Since climbing zero steps is outside the range of the stated problem, . . . .

The problem says that at any point, one or two steps can be climbed as a
single operation.  My solution for climbing zero steps does not say to perform
an operation of climbing zero steps, it says to perform zero operations. 

Each way of climbing 100 steps consists of a sequence of one's and two's that
add up to 100.  Similarly, a way of climbing zero steps consists of a sequence
of one's and two's that add up to zero.  The empty sequence meets these
criteria:  Every number in the sequence is one or two, and the sum of the
numbers in the sequence is zero.


				-- edp

How many times do you multiply five by itself to get one?  5^0 = 1.


				-- edp

Re .7:
Anything other than raising a number to a positive integral power makes no
sense at all in terms of multiplication. It is defined in some way to be
consistent with the primitive multiplication. 5^-1 = 1/5. How many times
do you multiply 5 by itself to get 1/5?

Similarly 0!=1 because it works out.

"God created the positive integers; all the rest is the work of man."

Re .6:

I am not saying that the null sequence will not yield a consistent
DEFINITION of f(0). I am saying that it is largely irrelevant and
also unnecessary. What is wrong with saying that it is Fibonacci with
first terms 1 & 2 and eschewing the metaphysics?

I am saying that there is a difference between saying:

1). It is trivially true for 0, when 0 is clearly in the domain of the
function.
    			and
2). There is only one way to climb zero steps.
    			or
3). There is only one sound that one hand clapping makes.

Re .0, .1 & .2:

.1 passes the conciseness criterion stated in .0.Neither .2 nor this wrangle
do. 

--------cjc-------

Re .8:

> I am not saying that the null sequence will not yield a consistent
> DEFINITION of f(0). I am saying that it is largely irrelevant and
> also unnecessary. What is wrong with saying that it is Fibonacci with
> first terms 1 & 2 and eschewing the metaphysics?

Using zero steps as a base of induction is simpler than use two steps.  We
could just as easily dispense with two steps and say that f(5) = 8 and
f(6) = 13.  We should use zero and one and not one and two for the same reasons
we should not use five and six.  Induction should begin at the beginning.

> 1). It is trivially true for 0, when 0 is clearly in the domain of the
> function.

I do not understand this statement.  What is "it"?

Consider this:

	A solution consisting of four operations (e.g., 1, 2, 2, 1) is valid.
	A solution consisting of three operations (e.g., 2, 1, 2) is valid.
	A solution consisting of two operations (e.g., 1, 1) is valid.
	A solution consisting of one operation (e.g., 2) is valid.

Why shouldn't a solution consisting of zero operations (e.g.) be valid?

Remember, the problem did not define the function f; I did.

Suppose the problem had said:

	A young [wo]man is climbing zero stairs. At any point [s]he can
	climb a single one or two stairs together. In how many different
	ways [s]he can choose to plan the trip up ? The answer can be
	explained in a single line (or two...)

What would the answer have been?

Re .0, .1 & .2:

> .1 passes the conciseness criterion stated in .0.Neither .2 nor this wrangle
> do.

.1 is less formal.  It also does not prove the sequence is the Fibonacci
sequence; it shows each number is the sum of the previous two but it does not
show the initial two numbers are the same as those of the Fibonacci sequence.

(Incidentally, I entered my reply not knowing .1 was there.)

You are on a step.  You wish to climb zero steps.  An operation consists of
climbing one or two steps.  You may perform as many operations as you wish.
How can you accomplish the goal of climbing zero steps?  If you perform zero
operations, then you have solved the problem.  This is important:  Performing
zero operations accomplishes the desired goal of climbing zero steps.  It is
perfectly valid.

To take this even further, my dictionary defines a Fibonacci number as a number
in the sequence 0, 1, 1, 2, 3, 5, . . . .  Perhaps we should now consider
f(-1).  You are on a step.  You wish to climb negative one steps.  How can
this be done?  Answer:  It can't.  Therefore, f(-1) = 0.

f(-1) and f(0) are both simpler cases than f(1) and f(2).  They are consistent
and they make sense.  f(1) and f(2) can be determined from f(-1) and f(0).


				-- edp

By the way, in .2, I said:

	Let f(x) denote the number of ways in which x steps can be climbed.

By this definition, f(-10) = f(-7) = f(3.14) = 0.  What should f(0) be?


				-- edp