Transcript NCTM Annual Meeting St. Louis, April 2006 Intersections of

NCTM Annual Meeting
St. Louis, April 2006
Intersections
of
Algebra and Counting
Duane DeTemple
Professor of Mathematics
Washington State University
Pullman WA
The NCTM Algebra
Standard
 All students should “Understand patterns,
relations, and functions.”
 To meet the grades 9 – 12 expectations,
students should “generalize patterns using
explicitly defined and recursively defined
functions.”
Preview of Coming
Attractions
 Multiplying Apples and Bananas:
How to Count by Polynomial
Multiplication
 Counting Trains: How to Count by
Obtaining Recurrence Relations
 Solving Recurrence Relations:
How to Find and Combine
Geometric Sequences to Obtain
Explicit Formulas
Multiplying Apples & Bananas
= AB
= A2 B
(
+
)
(1+
+
)(
=B+
2
B
+AB +
2
AB
= AB +
2
A
B
+
+
2
AB
)
+
2
2
AB
Packing a Lunch
How many ways can
up to 4 pieces of fruit
be put into the lunch
sack, where at least
one banana is
included?
Solving the Lunch Problem
B
2
B
AB
2
AB
2
AB
2
2
AB
(1+ +
)(
+
)
= B + B2 +AB + AB2 + A2B + A2B2
How many lunches include
exactly 3 pieces of fruit,
including at least one banana?
2
AB
2
XX
+
2
AB
2
XX
3
X
+
=2
2
2
(1 + X + X )(X + X )
2
3
4
= X + 2X + 2X + X
What lunch packing
problem is solved by
2
2
2
(1 + X + X )(X + X )(1 + X )
2
3
4
5
6
= X + 3X + 2X + 3X + 2X + X
?
A package
of 2
cookies
What polynomial
multiplication applies here?
Two
packages
with 2
cookies
each
(1  x  x  x  x )( x  x  x )(1  x  x )
2
0,1, …, 4
apples
3
4
1, 2, or 3
bananas
2
3
0, 2, or 4
cookies
2
4
How can polynomials be
multiplied easily?
Example
3  2x  4x
Synthetic Multiplication
3 2 4
2
5
2
2  5x
6  4 x  8x2
6
15 x  10 x  20 x
3
6  11x  2 x  20 x
3
2
2
6
4 8
15  10
20
11  2
20
Remark:
Synthetic Multiplication on TI-83
Input "áP",áP
Input "áQ",áQ
dim(áP)üM
ClrList áR
dim(áQ)üdim(áR)
For(J,1,M-1)
áR+áP(J)*áQüáR
augment({0},áQ)üáQ
augment(áR,{0})üáR
End
áR+áP(M)*áQüáR
Disp áR
Example
(1  x  x  x  x )( x  x  x )(1  x  x )
2
3
4
2
 x2 x 4 x 5 x 7 x
2
3
4
3
2
4
5
7 x  7 x  5 x  4 x  2 x + x
6
7
8
9
10
11
There are 5 ways to pack 8 items including up to 4
apples, at least 1 and up to 3 bananas, and up to 2
packages of cookies (2 cookies/package) :
A4B2C2, A3B1C4, A3B3C2, A2B2C4, A1B3C4
More Problems Solved By Multiplying Polynomials
A Postage Problem
You discovered you have
five 13¢, two 15¢, and
three 20¢ stamps.
Can you put 39¢ (exactly)
postage on a one-ounce
letter?
How about 63¢ for a twoounce letter?
Solving the Postage Problem
(1  x  x  x  x  x )
11
22
 1  x  x
15
33
40
60
 1 x 
11

2 x 
70
55

30
 1  x  x  x
20
44

x x
37
x 
63
x
145
40
Making Change
The till has just 3
nickels, 4 dimes, and 2
quarters.
Can you give out 75¢
in change?
Solution to Change Problem
1  x  x
2
x
3

Note:
Use
“nickels”
(5 cents)
as the
unit.
(1  x  x  x  x )
2
4
 1  x  x
5
 1
10
6
8

 3x 
15
x
21
Solutions of an Equation
With Integer Unknowns
How many solutions are there of the equation
a  b  2c  8
where
a  {0,1, 2,3, 4}
b  1, 2,3
c  0,1
Answer: 5
Train Counting
Let a d-train have
cars of lengths 1, 2,
… , n in some order.
How many trains, dn,
have total length n?
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
3+1
There are d4 = 8
trains of length 4.
1+3
4
Seeing a Pattern
d1 = 1
d2 = 2
d3 = 4
add a unit
length
caboose
stretch old
caboose to
get a caboose
of length > 1
Describing the d-train
pattern
dn1  dn  dn
d-trains
of length Add 1-car
caboose
n+1
to all
dn-trains
Stretch the
caboose of
all dn-trains
Conclusion:
The number of d-trains is
given by the doubling
geometric sequence
Explicit formula: d n  2
n 1
Recursion formula: d n 1  2d n ,
with initial condition d1  1
Counting f-trains
Let an f-train have
cars of lengths 1 and
2 in some order. How
many trains, fn , have
total length n ?
There are f4 = 5 trains
of length 4.
The Pattern of f-Trains
f 1= 1
f2 = 2
f3 = 3
add a
caboose of
length two
add a unit
length
caboose
Describing the f-train
pattern
fn2  fn1  fn
f-trains of
length
n+2
Add 1-car
caboose
to all
fn+1-trains
Add a 2car
caboose to
all fn-trains
Conclusion:
The number of f-trains is
given by the Fibonacci
sequence!
f n  Fn1
1, 1, 2, 3, 5, 8, 13, …
Counting p-trains
A p-train has an
engine of three types:
A, B, or C, and has
cars of lengths 2 or 3.
A 2-car cannot be
attached to engine C.
How many trains, pn,
have cars of total
length n?
p5 = 5
A
BA
-BC
-
More Cases of p-trains
AB-

p0= 3
p1= 0
C-
AB-
p2= 2
ABC-
p3= 3
AB-
ABp4= 2 AB-
p5= 5
C-
p-train sequence:
3, 0, 2, 3, 2, 5, …
What’s the pattern?
The Pattern of the p-trains
ABABC-
ABABC-
The Recurrence for p-Trains
pn3  pn1  pn
Add a
2-car
p-trains
of length caboose
to all
n+3
pn+1-trains
Add a
3-car
caboose to
all pn-trains
Foxtrot
Bill Amend, October 11, 2005
What should Jason say to
score a touchdown?
http://www.research.att.com/~njas/sequences/Seis.html
3,0,2,3,2,5,5,7
Search
Greetings from The On-Line Encyclopedia of Integer Sequences!
Search: 3,0,2,3,2,5,5,7
Displaying 1-1 of 1 results found.
A001608
Perrin sequence:
a(n) = a(n-2) + a(n-3).
3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68,
90, 119, 158, 209, 277, 367, 486, 644, 853, 1130,
An Amazing Property of
the Perrin Sequence
n
p(n)
0
3
1
0
2
2
3
3
4
2
5
5
6
5
7
8 9 10
7 10 12 17
n 11 12 13 14 15 16 17 18 19 20 21
p(n) 22 29 39 51 68 90 119 158 209 277 367
Theorem: For all primes n, n divides p(n).
Question: If n divides p(n), is n a prime?
Answer: No. The smallest example is
n = 271441 = 5212 divides p(271441)
Solving Recurrences
Problem: How do you solve
the Fibonacci RR?
xn2  xn1  xn
Idea: Look for solutions in the form
of geometric sequences xn = xn
x
n 2
x
n1
x
n
Divide out xn to get the quadratic
equation
x  x 1
2
Solve the quadratic to get the two roots
1 5
p
2
and
1 5
q
2
Thus
p  p 1
2
and
q  q 1
2
Multiply equations by any constants a
and b to get a general solution
xn  ap  bq
n
n
of the Fibonacci RR
xn2  xn1  xn
What are good choices for the
constants a and b?
The choice a = b = 1
Ln  p  q
n
n
L0  p  q  1  1  2
0
0
1 5 1 5
L1  p  q 

1
2
2
2, 1, 3, 4, 7, 11, 18, 29, 47,
1
1
This is the Lucas sequence, named
for Edouard Lucas (1842-1891).
The choice a = - b = 1/5
p q
Fn 
5
0
0
p  q 11
F0 

0
5
5
n
n
p  q 1 5 1 5
F1 


1
5
2 5
2 5
0, 1, 1, 2, 3, 5, 8, 13, 21,
1
1
This is the Fibonacci sequence!
Problem: How do you solve
the Perrin RR?
xn3  xn1  xn
Use the same idea: Look for solutions in
the form of geometric sequences xn = xn
x
n3
x
n1
x
n
Divide
x
n3
x
n1
x
n
by xn to get the cubic equation
x  x 1
3
Solve the cubic to get three roots
u, v, and w and the solution
au  bv  cw
n
n
n
where a, b, and c are any constants.
The choice a = b = c = 1 gives the solution
Pn  u  v  w
n
n
n
We see that
P0  u  v  w  1  1  1  3
0
0
0
P1  u  v  w  ?
1
1
1
and
P2  u  v  w  ?
2
2
2
Since u, v, and w are the roots of
x  x 1  0
3
we have that
x  x  1  ( x  u )  x  v  x  w 
3
 x  (u  v  w) x
3
2
(uv  uw  vw) x  uvw
Equate coefficients of x2 and x1
u  v  w  0, uv  uw  vw  1
Therefore,
P1  u  v  w  0
1
1
1
We also have that
0   u  v  w
2
 u  v  w  2  uv  uw  vw
2
2
2
 u  v  w  2  1
2
so
2
2
P2  u  v  w  2
2
2
2
Conclusion: the Perrin Sequence is given
either by the recurrence relation
Pn3  Pn1  Pn ,
P0  3, P1  0, P2  2
or explicitly by
Pn  u  v  w
n
n
n
where u, v, and w are the roots of the
cubic equation
x  x 1
3
For downloads of
 This PowerPoint presentation
 The paper
From Fibonacci to Foxtrot: Investigating
Recursion Relations with Geometric
Sequences
 TI-8X program to multiply
polynomials
Go to:
http://www.math.wsu.edu/math/faculty/detemple/