## A Toddler, Pascal and Fibonacci Climb Steps

Posted by mark schwartz on April 14, 2016

__Introduction__

I once taught a Contemporary Math class, designed as a survey course for those whose major required one math course but nothing heavy like a full Algebra, although some students had Pre-Algebra or Algebra in high school. Among the topics were binomial expansion, Pascal and Fibonacci. A student asked if these guys knew each other and when I asked him what he meant he said “I thought most of these guys stuff was connected somehow”. It wasn’t an elegant question but it turned out to be insightful. One of the exercises I had the class do was “a toddler climbs the steps”. As I thought about his question and the exercise and played with it some more I came to see a connection between these guys stuff. As a class we discussed our way through the story that follows and learned considerably more because his question led us to it.

__The Story__

Let’s start with a set of steps and a toddler. The toddler is about to climb a set of steps but is limited to two ways; either 1 step at a time or 2 steps at a time, or a combination of 1-step and 2-step climbing.

The question is how many different ways the toddler might climb a fixed number of steps. What this means, for example, is … suppose there are only 2 steps. The toddler could climb 1 step at a time, which can be represented as 1.1, for a total of 2. The toddler could also simply climb the 2 steps once.

Continuing this, if the toddler were to climb 3 or 4 or 5 etc., the number of ways to climb can be determined by simply mapping the possibilities and counting them. To clarify the entries in the “ways-to-climb” column in the table below, take a look at the ways-to-climb for 3 steps. “1.1.1” means that the baby climbed them 1 at a time. “1.2” means that the baby climbed one step followed by a 2-step climb and “2.1” means the baby first climbed 2 at a time, followed by climbing one. These are the only 3 ways that the baby could climb 3 steps.

__# steps__ __Ways to climb__ __Total__

1 1 1

2 1.1 2 2

3 1.1.1 1. 2 2.1 3

4 1.1.1.1 1.1.2 1.2.1 2.1.1 2.2 5

5 1.1.1.1.1 1.1.1.2 1.1.2.1 1.2.1.1 2.1.1.1 2.2.1 2.1.2 1.2.2 8

6 1.1.1.1.1.1 1.1.1.1.2 1.1.1.2.1 1.1.2.1.1 1.2.1.1.1 2.1.1.1.1 2.2.1.1

2.1.2.1 2.1.1.2 1.1.2.2 1.2.1.2 1.2.2.1 2.2.2 13

An interesting and familiar pattern shows up in the “Total” column. It’s the Fibonacci series. But the question is “why’? This question can be answered by looking first at the relationship between Pascal’s triangle and the Fibonacci series.

Pascal’s triangle is a series of rows showing the coefficients of the terms that result from the expansion of the binomial

(x + y)^{n} using n = 0 through 6. which will generate 7 rows. Pascal’s triangle, left aligned, is:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

The Fibonacci series is found in the triangle by starting at a “1” in the left-hand column, adding the numbers as you move *diagonally up left to right *at about 45 degrees. For example;

In the fifth row, moving diagonally up, there is a 1, 3, 1, totaling 5.

In the sixth row, moving diagonally up, there is a 1, 4, 3, totaling 8.

In the seventh row, moving diagonally up, there is a 1, 5, 6, 1, totaling 13.

These are a sequence in the Fibonacci series.

But the pattern goes even deeper. Pascal’s triangle only shows the coefficients of the terms in the expansion. For example, the expansion of ( x + y )^{3} is x^{3 } + 3x^{2}y + 3xy^{2} + y^{3}, which are the coefficients in the fourth row of Pascal’s triangle. What the baby climbing the steps does is show the pattern, somewhat hidden, of the expansion and further, shows how the Fibonacci series can be seen in the triangle.

Let’s begin with the number of steps = 2. In this case, and in all subsequent cases, let 1 step = x and 2 steps = y. For 2 steps then the outcomes in the ways-to-climb column would be x.x and y, not 1.1 and 2. Here we will use exponential notation for x.x giving x^{2} and this will be done for all subsequent cases.

So, for 2 steps that has 2 outcomes, they are x^{2 }and y. Now look at Pascal’s triangle and the Fibonacci series that can be generated from it.

An expansion of ( x + y )^{1} gives x + y

An expansion of ( x + y )^{2}^{ }gives x^{2} + 2xy + y^{2}

An expansion of ( x + y )^{3} gives x^{3} + 3x^{2}y + 3xy^{2} + y^{3}

An expansion of ( x + y )^{4 } gives x^{4} + 4x^{3}y + 6x^{2}y^{2} + 4xy^{3} + y^{4}

The expansions have been “spaced” so that you can see that if you add the coefficients of x^{2} in the second expansion and the coefficient of y in the first expansion you get 2. If you add the coefficients x^{3} and 2xy you get 3. If you add the coefficients of x^{4}, 3x^{2}y and y^{2 }you get 5 and 2, 3, 5 are a sequence in the Fibonacci series.

Below in rows 1 and 2 is an example showing the generation of the relationship between “ways to climb” when the toddler climbing 5 steps. Row two is the first term of (x + y)^{5 }, the second term of (x + y)^{4} and the third term of (x + y)^{3}. This is the same as what you get moving diagonally up in Pascal’s triangle.

Row 1. Ways to climb 1.1.1.1.1 1.1.1.2 1.1.2.1 1.2.1.1 2.1.1.1 2.2.1 2.1.2 1.2.2

Row 2. xy form x^{5} 4x^{3}y 3xy^{2}

If you add the coefficients of the terms in row 2 above you get 8, which is the same as finding the Fibonacci series from Pascal’s triangle beginning in the sixth row of the above Pascal’s triangle. What’s more, row 2 demonstrates the relationship between the coefficients in Pascal’s triangle, the number of ways the toddler can climb steps, the terms in a binomial expansion and finally, the Fibonacci series. You can see that the entries in row 1- each term having 1s and 2s – are, in essence, the exponents of x and y in row 2, where 1 step = x and 2 steps = y. At the beginning of this piece, I noted that you could find the number of ways by mapping it, but given climbing steps is connected to the binomial expansion, use the binomial expansion. For example, if there were 10 steps, in how many ways could the toddler climb these 10 steps?

** Here’s how get the number of steps**; generate a series of combinations using

_{n}C

_{r}because that’s how you can get the coefficients of the terms in a binomial expansion. For example given x

^{2}y

^{2},

_{2}C

_{2}gives 6. But it’s not a single calculation.

Knowing that the Fibonacci series is the “Total” outcome as seen in Table 1 and also that the Fibonacci series is the outcome by moving diagonally up at 45^{0} in Pascal’s triangle, the _{n}C_{r} calculation is a series of calculations using the following pattern:

**Start with _{10}C_{0 }and generate the series by decreasing “n” by 1 and increasing “r” by 1 each time**. In this case, the next two terms would be

_{9}C

_{1 }followed by

_{8}C

_{2}, etc..

The question then is “how do you know when to stop”? At some point in generating this series, r will be greater than n and since this is illegal (your calculator will tell you!), you’re done. Just add up the values that have been generated. Given 10 steps, there are 89 different ways for the toddler to climb them. This may seem awkward, but as I indicated earlier, you could map the outcomes but in this case and with larger numbers it would be very time consuming and very trying to map it. Stick with _{n}C_{r}.

As I noted in the introduction we learned a lot as we worked through this. More importantly though, in my opinion, was the engagement of the class in doing the work and seeing all the connections. It didn’t exactly follow the curriculum, but it did follow a student’s imaginative question.

You can leave a comment below if you’d like to … it would be appreciated.

## Leave a Reply