# Integer Sequences I: The Fibonacci Sequence

## Introductory Remarks

This lesson could be subtitled "Guess my rule." I write a sequence of four or five numbers on the board. I then ask the students what number comes next. After the students have correctly added two or three numbers, I ask what rule they are using to figure out the next number in the sequence. In determining the rule, I remind them that the rule must work for every number in the sequence.

I have taught this lesson to second and third graders.

## Supplies

In addition to a chalkboard, you will need pieces of paper, about a quarter of a sheet, enough to give each student three pieces.

## Lesson Plan

1. Write the numbers 1 3 5 7 on the chalkboard.
2. Ask the students what number comes next. Usually a student will correctly guess 9.
3. Ask for the next number in the sequence. Ask the student who answers how she or he knew that was correct. Students will offer explanations such as "You're skipping a number every time." If they don't bring it up themselves, point out that these are the odd numbers.
4. Write the numbers 1 4 7 10 on the board. Ask for the next number (13). Ask for the number after that (16). Ask the students to explain the pattern.
5. Write the numbers 1 2 4 7 11 on the board. Ask for the next number. It may take a few guesses for the students to come up with the correct answer of 16. Ask for the next number (22). Ask the students to explain the pattern.

It may take several minutes for the students to figure out this pattern. Often they will say, "You're skipping two numbers." I respond by referring to the sequence and asking whether I am skipping two numbers between 1 and 2. I then ask what is happening between 2 and 4. As we proceed along the sequence a few students will guess the rule. They usually express it as "skipping one, then you skip two, then you skip three."

It is important when discussing these explanations to take all suggested rules seriously, and to try to apply them to the pattern. I avoid labelling ideas as "right" and "wrong." Sometimes a student will come up with a new rule that fits the pattern. I tell the student that it is a good rule, but it is not the one I had in mind.

6. Write the numbers 1 3 6 10 on the board. Ask the students what comes next. After they discover the next two numbers, 15 and 21, ask them to explain the rule. They usually figure this out pretty quickly, since it is the same as the rule for the preceding sequence.
7. Draw three dots on the board, with one dot on top, and two dots in a row below so that all three form a triangle. Cover the lower two dots, and tell the students that here is one, then uncover the dots and ask them to count. Draw a row of three dots below the row of two, and ask the students to count the total number of dots. Add a row of four dots, then a row of five dots, counting each time. You are building a triangular array. Tell the students that the numbers 1 3 6 10 15 . . . are sometimes called the triangular numbers.
8. Now it's time for the challenge. Write the numbers 1 1 2 3 5 on the board. Ask the students what comes next. You should get wildly varying responses. To involve all of the students, pass out squares of paper, and have each student write his or her guess in large digits so you can see it. Have the students hold their guesses up in the air. I read the guesses out loud. It generally comes out, "I see a 5, and a seven, and another 7, and an 8, and there's a 10, and more sevens . . ."

Add the number 8 to the sequence, and ask the students to write a guess for the next number (13).

Have the students guess one more number (21).

Ask the students if they can figure out the rule. I've had a number of third graders and an occasional second grader get this one. To get the next number in the sequence, you add the previous two numbers, i.e. 1+1=2, 1+2=3, 2+3=5, and so on. This is called the Fibonacci sequence.

# Integer Sequences II: Combinatorics

## Supplies

Each student will need a piece of scratch paper--a half sheet will do--and a pencil.

## Warm-up: Guess my rule

1. Write the number sequence 1 3 5 7 on the board. Ask the students what number comes next. Add 9 to the sequence. Ask for the next number. Add 11 to the sequence. Ask if the students know the special name for the sequence. If they don't know, tell them these are the odd numbers.
2. Write the number sequence 1 2 4 8 on the board below the odd numbers. Ask for the next number (16), and the next (32). Ask the students to explain the rule that generates the sequence (doubling the previous number.) Tell them these are the binary numbers.
3. Write the number sequence 1 3 6 10 under the binary numbers. Ask for the next number (15), and the next (21). Ask the students to figure out the rule. (Add 2, then 3, then 4, and so on, to the previous number.) Tell the students that these are called the triangular numbers. If they haven't seen this sequence before, draw a triangular array of dots on the board with 1 dot in the first row, 2 dots in the second row, 3 dots in the third row, and so on. Show that the number of dots above any particular row is 1, 3, 6 . . .
4. Write the number sequence 1 4 9 16 on the board. Ask the students to guess the next number (25), and the next (36). Ask them to figure out the rule. Two explanations are possible: Adding successive odd numbers, 3, 5, 7 . . . to the previous number, or squaring 1, 2, 3, 4 . . . Tell students these are the square numbers.

### The handshake puzzle

Pose the following problem: A baseball team is practicing for the first time. In order to get to know each other, the players shake hands. Each player shakes hands with every other player exactly once. How many total handshakes are there?

Have the students guess the answer, and write their guesses on the sheets of scratch paper. Tell them to put the paper aside.

Now work it out inductively. Begin by calling two students to the front of the room and having them shake hands. Draw a table on the board. Label the left column "number of players" and the right column "handshakes." Write 2 and 1 in the left and right columns respectively.

Have three students come to the front of the room and shake hands with each other. Count the handshakes (3) and add the numbers to the table.

Continue with four students, five students, and six students. You may need to impose a bit of order on the handshakes to make sure they get counted correctly. You should get 6, 10 and 15.

Ask the students if they recognize the numbers in the right-hand column. They should identify them as the triangular numbers.

Use the rule for generating triangular numbers to work out the seventh (21), eighth (28), and ninth (36) numbers in the sequence. Have the students compare their guesses to the answer you worked out with them.

# Pascal's Triangle

## Introductory remarks

This is one of my most popular lessons.

Pascal's triangle, named after the seventeeth-century French mathematician Blaise Pascal, turns up in a number of mathematical problems. Those who remember their high school algebra will recognize the numbers as binomial coefficients. If you are familiar with probability theory, you may know that these numbers give the probability of tossing m heads (or tails), in n tosses.

## Lesson Plan

1. Draw the following street map on the chalkboard: At the top in the middle is the main corner, or starting point. The two boundary streets run at 45-degree angles down from the starting point, one to the right, and one to the left. Inside these boundaries draw a square grid, fairly widely spaced, of lines parallel to, and ending at, these boundary streets. If this description confuses you, take a piece of graph paper, rotate it 45 degrees so that one corner is at the top, and copy a 6-by-6 square of it. I space the "streets" about 6 inches apart.
2. Pose the problem. Starting at the top of the grid, you want to know how many different paths there are from the starting point to any corner, subject to the following conditions. All paths must follow streets, and you are only permitted to move downward, either to the right, or to the left.
3. Begin with the first row of intersections below the starting point. Show that there is only one path to each of these intersections. Write the number 1 on each intersection.
4. Move on to the next row of three intersections. Ask the students how many paths there are to the leftmost intersection in that row. Ask them to describe the path by telling you which direction to take at each intersection. Starting at the top, you move down to the left, which takes you to the leftmost intersection in row two. Then you move to the left again, taking you to the intersection you are trying to reach. This path is therefore "left-left."
5. Have the students describe the paths leading to the middle intersection in row three. The two legal paths are "left-right" and "right-left." Next, have them find the only path to the rightmost intersection, "right-right."
6. Proceed to the fourth row, with four intersections. This is where the puzzle starts to get interesting. By this time, most students will realize that there is only one legal path to any intersection on the right or left boundary. Don't tell them how many paths to look for in the middle. As they describe paths, write them down using the letters L and R, for example LLR for "left-left-right." Have the students continue to look for paths until both you and they are satisfied that they have found them all. (You, of course know that the three legal paths for the second intersection in the row are LLR, LRL, and RLL.) The students may use symmetry to conclude that the number of paths to the third intersection in the row is equal to the number of paths to the second intersection, or they may need to list them (LRR, RLR, and RRL.)
7. Continue with the next row. The numbers of paths to the fifth row intersections are 1 4 6 4 1.
8. Summarize by writing in the form of a triangle the numbers discovered so far:
------------1-------------
----------1---1-----------
--------1---2---1---------
------1---3---3---1-------
----1---4---6---4---1-----

Ask the students if they see a pattern that will generate the next row of numbers. Most students quickly figure out that the first two numbers in the row are 1 5, and the last two are 5 1. Some students can guess the rule: add the two numbers above to get the next number. Thus 1+1=2, 2+1=3, 1+3=4, 3+3=6. Applying this rule, the middle numbers of the sixth row are 10 10. If students do not figure the rule out in a few minutes, I tell them.

9. Tell the students this pattern is called Pascal's Triangle. Tell them it comes up in a number of mathematical contexts, the two most common areas being the probability of coin tosses, and the expansion of binomials in high school algebra.

## Follow-Up Activity: Probability of Coin Tosses

### Supplies

Each student will need four pennies.

### Lesson Plan

1. Ask the students if they know what "odds" are. If they don't, explain that odds are numbers that give the relative likelihood of events. For example, when tossing one penny, the chances of getting heads or tails are equally likely. Thus the odds are 1:1.
2. Test the prediction by having each student toss one coin. Count the numbers of heads and tails. Explain to the students that experimental results do not always match the theoretical probability.
3. Now ask the students to list the possible outcomes of tossing two coins. (They should come up with two heads, two tails, and one head/one tail.) Explain that order matters here, so that HT and TH add together to double the odds. Thus the odds for HH HT/TH TT are 1:2:1.
4. Test the prediction by having each student toss two coins.
5. Have the students figure out all the possible outcomes of tossing three coins. (They are HHH, HHT, HTH, THH, HTT, THT, TTH, and TTT.) Write down the theoretical odds 1:3:3:1. Test the prediction by having the students toss three coins.
6. Figure out the possible outcomes for tossing four coins. (HHHH, HHHT, HHTH, HTHH, THHH, HHTT, HTHT, HTTH, THHT, THTH, TTHH, HTTT, THTT, TTHT, TTTH, TTTT.) The theoretical odds are 1:4:6:4:1. Test the prediction by tossing four coins.
7. Write the odds in triangular format:
----1:1----
---1:2:1---
--1:3:3:1--
-1:4:6:4:1-

Ask the students where they have seen this before. They will recognize Pascal's triangle from the street map puzzle.

# Generalized Fibonacci Sequences and the Golden Mean

### Supplies

Students will each need a calculator for this activity.

### Lesson Plan

1. Write the number sequence 1 1 2 3 5 on the board. Ask the students what comes next. If they don't get it in three or four guesses, tell them the next number is 8. Have them guess the next number (13), and the next (21). Ask them if they can figure out the rule that tells how to generate the next number in the sequence. (The rule is to add the previous two numbers.)
2. Have the students calculate about 12 more terms of the sequence. They may do this mentally, on paper, or with a calculator.
3. Have the students divide the next term by the next-to-the-last term of the sequence. It will be approximately 1.618. Write this number on the board.
4. Start a new sequence by choosing any two numbers between 1 and 20. It does not matter if the second number is smaller than the first. Apply the Fibonacci rule of adding the previous two numbers until you have a sequence of 20 numbers.
5. Have the students divide the last number in the sequence by the next-to-the-last number. Again the result will be approximately 1.618. Explain that this number is called the "golden ratio" or the "golden mean." According to the ancient Greeks, a rectangle with its sides in this ratio was the most beautiful rectangle a person could draw.