Patterns
The Border Problem Revisted
Solution
We will study a well known problem (often called the Border Problem) from several points of view.
10 / n8 / m
10 / 8 / n / m
Figure 1 / Figure 2
Assume that all (linear) dimensions are given in feet and that in Figure 2 both n and m are whole numbers, with n = m + 2 (or m = n – 2). We might think of the interior (the white portion) is a pool or garden while the border (the shaded portion) consists of 1 ft x 1 ft square tiles. We are interested ways to determine the number of square tiles on the border of the shape.
a) Without counting, use the information given in Figure 1 (exterior is a 10x10 square; interior is an 8x8 square; the border is made up of 1x1 squares) to determine the number of squares needed for the border. If possible, find more than one way to describe the number of border squares. Record the different ways you discover in the middle column of the chart below.
b) Without counting, use the information given in Figure 2 (exterior is a nxn square; interior is a mxm square; m, n are whole numbers with n = m + 2) to determine the number of squares needed for the
c) border. If possible, find more than one way to describe the number of border squares. Record the different ways you discover in the chart below, using the left column if your answer involves n and using the right column if your answer involves m. Use the row that corresponds to the concrete answer you gave in part a using 10 ft and 8 ft as the dimensions in Figure 1.
d) Find a geometric explanation corresponding to the computations given in each row below.
Answers involving n Answers involving 8 & 10 Answers involving m
Example 1: If n is the exterior dimensions of our square, then , where m is the interior dimension. The number of tiles needed for the border can be given as where . Look at this sequence of numbers and try to think of another way to generate this sequence. This time think in terms of the previous term in the sequence. Create a table with the sequence. Notice that the number of tiles needed for is four more than the previous number of tiles, . In general, we can define a recursive rule for the number of tiles to be:
, for.
Definition: A function f whose domain is N (the Natural Numbers) is called an infinite sequence and its range is Rf = {f(n) | n N. The notation for sequences is usually written in the form where for nN.
Sometimes it is more useful to start the “indexing” of values in the sequence with some number other than 1. For example, we might write for nN and . Another example might be for nN and . To permit these situations, we generalize our definition to say that a sequence is a function whose domain is where the symbol denotes the integers.
Definition: If we have a formula, f(n), for the nth term of a sequence, then we say that we have an explicit rule for the function.
Definition: If a sequence is given by a rule that describes the relationship between consecutive terms of the sequence, then we have a recursive rule or pattern for the sequence.
Definition: A sequence possessing the property that each term is obtained by adding a fixed real number d (called the common difference) to the previous terms is called an arithmetic sequence.
Comment: We have just seen that in the Border Problem to be a linear function whose domain is the positive integers greater than or equal to 3.
Fact: If a sequence f is an arithmetic sequence then f is a linear function whose domain is N or {nZ | n n0 for some fixed value n0}. The converse is also true: If a sequence f is a linear function whose domain is the positive integers, then f is an arithmetic sequence. Moreover, the common difference d is the slope of the line defined by f. See Algebra Connections for an explanation of this fact.
Example 2: Cafeteria Problem. Algebra Connections
A middle grade cafeteria has square tables where students can eat lunch in groups of four. If six students want to eat at the same table, then two square tables can be pushed together to accommodate a group of this size, and even larger groups can be handled by joining together more tables in a straight line.
a) Fill in the missing data in the table
n = number of square tablespushed together in a line / S(n) = Sn = number of students sitting at n tables
1 / 4
2 / 6
3
4
5
6
b) Describe in words the table-joining pattern. How would you find the number of students sitting at n tables?
c) Describe in symbols how you would find the number of students sitting at n tables.
d) Determine the number of students that can sit together in a table formed by joining 17 square tables in a line.
e) What is the smallest number of square tables that could be pushed together in a line so as to seat 51 students? (Some chairs might not be used.)
f) Challenge yourself to find an explicit rule and a recursive rule. In part c) you found one type of rule, now find the other type of rule.
Example 3: Landscape Brick Problem. Algebra Connections
We want to line a driveway with 6” by 12” rectangle landscape blocks so that the height of the border is 12” tall. We would also like the block border to be made by repeating a fixed block configuration of width 6n inches. The figures below illustrate that there is only one 6” width configuration, two 12” width configurations, and three 18”width configurations.
= number of block configurations of width 6n inches and height 12 inches
a) Determine the number of different 24”, 30”, and 36”, width block configurations.
b) Write a recursive rule describing the sequence of block configurations.
c) Explain why your recursive rule makes sense.
Example 4: The Fibonacci sequence is defined recursively as:
for .
Using the rule, write the first 10 terms for the Fibonacci sequence.
Is there an explicit formula for the Fibonacci numbers?
Yes!! See Algebra Connections for more information about the explicit rule for the Fibonacci sequence.
Euler (pronounced Oiler) in 1765 discovered an explicit rule for the nth term of the Fibonacci sequence. In 1843, Jacques Binet derived the same formula as Euler. The explicit formula is referred to as Binet’s Formula.
for each integer .
Calculate and using Binet’s Formula.
Example 5: Groups of People
Define Pn to be the total number of groups of people that could be formed from a set of n people.
For example: Suppose n = 3. Let A = Anne, B = Bryan and D = Dean. We want to determine the number of subsets that can be formed from the set {A, B, D}. Let’s list them:
{A}, {B}, {D}, {A,B}, {A,D}, {B,D}, {A,B,D},
Note: denotes the empty set which is a set of people consisting of no members.
So, P3 = 8.
a) Complete the table below.
n = number of people / Pn = number of groups of peopleformed from a set of n people
1
2
3 / 8
4
b) Describe in words how to find the number of subgroups of people formed from a set of n people.
c) Write a recursive rule describing the pattern.
d) Write an explicit rule representing the pattern.
Definition: A sequence where each successive term is obtained by multiplying the previous term by a fixed (nonzero) number is called a geometric sequence, and the fixed (nonzero) number is called the common ratio. Let . The nth term of a geometric sequence with a common ratio r (nonzero) is given by or if .
Fact: The sum of a finite geometric sequence is denoted by and can be found by the formula if .
Let’s see why this fact is true:
/ (Multiply the top equation above by r.)/ (Subtract the 2 equations)
/ (combine like terms)
/ (factor out on the left side and factor out on the right side)
/ (divide both sides by , note )
Example 6: Pennies Add Up
Suppose you put 2 cents in a jar today, and each day thereafter you triple the amount that you put in the previous day.
a) Using recursive notation express the amount you put in as Mn on day n.
b) How much would you put in the jar on the 17th day?
c) How much would you have saved after 17 days?
Example 7: High Fives (modification of Handshake problem)
After a sports event, the opposing teams line up and shake hands. To celebrate their victory, members of the winning team may congratulate each other with a round of high fives. In this problem, you will explore the total number of handshakes or high fives that take place. Consider the following case where each member of the team gives a high five to each teammate.
a) How many high fives will take place among an academic quiz team with 4 members?
b) How many high fives will take place among a golf team with 12 members?
c) Describe in words how to find the number of high fives for a team with n members.
d) Write a rule for the number of high fives, Hn, that will take place among a team with n members.
e) Your rule in part d) was either a recursive or explicit rule. Try to write the other type of rule.
Example 8: Find the next term in the sequence: 1, 5, 9, 13, 17, … (Warning!)
a) Neil Sloane’s On-Line Encyclopedia of Integer Sequences is an excellent resource for exploring sequences of integers. It can be found on the Web at http://www.research.att.com/~njas/sequences/index.html Go to this web site and type in the first five terms of the sequence 1, 5, 9, 13, 17, … and click on the Search button. How many sequences did you find?
b) Which sequence corresponds to the one you chose?
c) List the first 7 terms of the sequence of odd integers that can be written in the form for integers and. Note that and can be any integer values, but the resulting sum must be an odd number.
d) Explain why it is not a good idea to define a sequence by listing its first few terms.
Patterns - page 9