Fun lecture on geometric series (Part 2): Ways of counting money

Every once in a while, I’ll give a “fun lecture” to my students. The rules of a “fun lecture” are that I talk about some advanced applications of classroom topics, but I won’t hold them responsible for these ideas on homework and on exams. In other words, they can just enjoy the lecture without being responsible for its content.

This series of posts describes a fun lecture that I’ve given to my Precalculus students after they’ve learned about partial fractions and geometric series.

In the 1949 cartoon “Hare Do,” Bugs Bunny comes across the following sign when trying to buy candy (well, actually, a carrot) from a vending machine. The picture below can be seen at the 2:40 mark of this video: http://www.ulozto.net/live/xSG8zto/bugs-bunny-hare-do-1949-avi

How many ways are there of expressing 20 cents using pennies, nickels, dimes, and (though not applicable to this problem) quarters? Believe it or not, this is equivalent to the following very complicated multiplication problem:

$\left[1 + x + x^2 + x^3 + x^4 + x^5 + \dots \right]$

$\times \left[1 + x^5 + x^{10} + x^{15} + x^{20} + x^{25} + \dots \right]$

$\times \left[1 + x^{10} + x^{20} + x^{30} + x^{40} + x^{50} + \dots \right]$

$\times \left[1 + x^{25} + x^{50} + x^{75} + x^{100} + x^{125} + \dots \right]$

On the first line, the exponents are all multiples of 1. On the second line, the exponents are all multiples of 5. On the third line, the exponents are all multiples of 10. On the fourth line, the exponents are all multiples of 25.

How many ways are there of constructing a product of $x^{20}$ from the product of these four infinite series? I offer a thought bubble if you’d like to think about it before seeing the answer.

There are actually 9 ways. We could choose $1$ from the first, second, and fourth lines while choosing $x^{20}$ from the third line. So,

$1 \cdot 1 \cdot x^{20} \cdot 1 = x^{20}$

There are 8 other ways. For each of these lines, the first term comes from the first infinite series, the second term comes from the second infinite series, and so on.

$1 \cdot x^{10} \cdot x^{10} \cdot 1 = x^{20}$

$1 \cdot x^{20} \cdot 1 \cdot 1 = x^{20}$

$x^{10} \cdot 1 \cdot x^{10} \cdot 1 = x^{20}$

$x^5 \cdot x^{15} \cdot 1 \cdot 1 = x^{20}$

$x^{10} \cdot x^{10} \cdot 1 \cdot 1 = x^{20}$

$x^5 \cdot x^{15} \cdot 1 \cdot 1 = x^{20}$

$x^{20} \cdot 1 \cdot 1 \cdot 1 = x^{20}$

$x^5 \cdot x^5 \cdot x^{10} \cdot 1 = x^{20}$

The nice thing is that each of these expressions is conceptually equivalent to a way of expressing 20 cents using pennies, nickels, dimes, and quarters. In each case, the value in parentheses matches an exponent.

$1 \cdot 1 \cdot x^{20} \cdot 1 = x^{20}$ : 2 dimes (20 cents).
$1 \cdot x^{10} \cdot x^{10} \cdot 1 = x^{20}$ : 2 nickels (10 cents) and 1 dime (10 cents)
$1 \cdot x^{20} \cdot 1 \cdot 1 = x^{20}$ : 4 nickels (20 cents)
$x^{10} \cdot 1 \cdot x^{10} \cdot 1 = x^{20}$ : 10 pennies (10 cents) and 1 dime (10 cents)
$x^{15} \cdot x^5 \cdot 1 \cdot 1 = x^{20}$ : 15 pennies (15 cents) and 1 nickel (5 cents)
$x^{10} \cdot x^{10} \cdot 1 \cdot 1 = x^{20}$ : 10 pennies (10 cents) and 2 nickels (10 cents)
$x^5 \cdot x^{15} \cdot 1 \cdot 1 = x^{20}$ : 5 pennies (5 cents) and 3 nickels (15 cents)
$x^{20} \cdot 1 \cdot 1 \cdot 1 = x^{20}$ : 20 pennies (20 cents)
$x^5 \cdot x^5 \cdot x^{10} \cdot 1 = x^{20}$ : 5 pennies (5 cents), 1 nickel (5 cents), and 1 dime (10 cents)

Notice that the last line didn’t appear in the Bugs Bunny cartoon.

Using the formula for an infinite geometric series (and assuming $-1 < x < 1$ ), we may write the infinite product as

$f(x) = \displaystyle \frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})}$

When written as an infinite series — that is, as a Taylor series about $x =0$ — the coefficients provide the number of ways of expressing that many cents using pennies, nickels, dimes and quarters. This Taylor series can be computed with Mathematica:

Looking at the coefficient of $x^{20}$ , we see that there are indeed 9 ways of expressing 20 cents with pennies, nickels, dimes, and quarters. We also see that there are 242 of expressing 1 dollar and 1463 ways of expressing 2 dollars.

The United States also has 50-cent coins and dollar coins, although they are rarely used in circulation. Our answers become slightly different if we permit the use of these larger coins:

Finally, just for the fun of it, the coins in the United Kingdom are worth 1 pence, 2 pence, 5 pence, 10 pence, 20 pence, 50 pence, 100 pence (1 pound), and 200 pence (2 pounds). With these different coins, there are 41 ways of expressing 20 pence, 4563 ways of expressing 1 pound, and 73,682 ways of expressing 2 pounds.

For more discussion about this application of generating functions — including ways of determining the above coefficients without Mathematica — I’ll refer to the 1000+ results of the following Google search:

https://www.google.com/search?q=pennies+nickles+dimes+quarters+%22generating+function%22

FYI, previous posts on an infinite geometric series:

https://meangreenmath.com/2013/09/16/formula-for-an-infinite-geometric-series-part-9

https://meangreenmath.com/2013/09/17/formula-for-an-infinite-geometric-series-part-10

https://meangreenmath.com/2013/09/18/formula-for-an-infinite-geometric-series-part-11

Previous posts on Taylor series:

https://meangreenmath.com/2013/07/01/reminding-students-about-taylor-series-part-1/

https://meangreenmath.com/2013/07/02/reminding-students-about-taylor-series-part-2/

https://meangreenmath.com/2013/07/03/giving-students-a-refresher-about-taylor-series-part-3/

https://meangreenmath.com/2013/07/04/giving-students-a-refresher-about-taylor-series-part-4/

https://meangreenmath.com/2013/07/05/reminding-students-about-taylor-series-part-5/

https://meangreenmath.com/2013/07/06/reminding-students-about-taylor-series-part-6/