Marveling At The Historical

Math Oldies But Goodies

  • About This Blog

    This blog is mostly about math procedures in textbooks dated from about 1825-1900. I’m writing about them because some of the procedures are exquisite and much more powerful, and simpler, than some of the procedures in current text books. Really!

    I update this blog as frequently as possible ... every 2-3 days. And, if you are a lover of old texts and unique procedures, you might want to talk to me about them, at markdotmath@gmail.com. I’m not an antiquarian; the books I have are dusty, musty, brown-paged scribbled-in texts written by authors with insights into how math works. Unfortunately, most of their procedures have vanished. They’ve been overcome by more traditional perspectives, but you have to realize that at that time, they were teaching the traditional methods.

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   x3 + 3x2y + 3xy2 + y3, 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 x2 and this will be done for all subsequent cases.

So, for 2 steps that has 2 outcomes, they are x2 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        x2   +   2xy +   y2

An expansion of ( x + y )3 gives          x3 +  3x2y +  3xy2 +  y3

An expansion of ( x + y )4 gives          x4 +   4x3y + 6x2y2 + 4xy3 +  y4

The expansions have been “spaced” so that you can see that if you add the coefficients of x2 in the second expansion and the coefficient of y in the first expansion you get 2. If you add the coefficients x3 and 2xy you get 3. If you add the coefficients of x4, 3x2y and y2 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                   x5                                         4x3y                                                     3xy2

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 nCr because that’s how you can get the coefficients of the terms in a binomial expansion. For example given x2y2, 2C2 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 450 in Pascal’s triangle, the nCr calculation is a series of calculations using the following pattern:

Start with 10C0 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 9C1 followed by 8C2, 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 nCr.

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.

 

 

 

 

 

 

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: