Fun lecture on geometric series (Part 5): The Fibonacci sequence

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.

In this series of posts, I’m describing a fun lecture on generating functions that I’ve given to my Precalculus students. In the previous post, we looked at the famed Fibonacci sequence

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots

We also looked at that (slightly less famous) Quintanilla sequence

1, 1, 3, 5, 11, 21, 43, 85, \dots

which is defined so that each term is the sum of the previous term and twice the term that’s two back in the sequence. Using the concept of a generating function, we found that the nth term of the Quintanilla sequence is

Q_n = \displaystyle \frac{2^{n+1} + (-1)^n}{3}

green line

To close out the fun lecture, I’ll then verify that this formula works by using mathematical induction. As seen below, it’s a lot less work to verify the formula with mathematical induction than to derive it from the generating function.

n=0: Q_0 = \displaystyle \frac{2+1}{3} = 1.

n = 1: Q_1 = \displaystyle \frac{2^2-1}{3} = 1.

n-1 and n: Assume the formula works for Q_{n-1} and Q_n.

n+1:

Q_{n+1} = Q_n + 2 Q_{n-1}

Q_{n+1} = \displaystyle \frac{2^{n+1} + (-1)^n}{3} + 2 \cdot \frac{2^n + (-1)^{n-1}}{3}

Q_{n+1} = \displaystyle \frac{2^{n+1} + (-1)^n + 2 \cdot 2^n + 2 \cdot (-1)^{n-1}}{3}

Q_{n+1} = \displaystyle \frac{2^{n+1} + 2^{n+1} + (-1)^n - 2 \cdot (-1)^n}{3}

Q_{n+1} = \displaystyle \frac{2 \cdot 2^{n+1} - (-1)^n}{3}

Q_{n+1} = \displaystyle \frac{2^{n+2} + (-1)^{n+1}}{3}

That’s the formula if n is replaced by n+1, and so we’re done.

Let me note parenthetically that the above simplification is not all intuitive when encountered by students for the first time — even really bright students who know the laws of exponents cold and who know full well that x + x = 2x and x - 2x = -x. That said, I’ve found that simplifications like 2^{n+1} + 2^{n+1} = 2 \cdot 2^{n+1} = 2^{n+2} are usually a little intimidating to most students at first blush, though they can quickly get the hang of it.

green line

By this point, I’m usually near the end of my 50-minute fun lecture. Since students are not responsible for replicating the contents of the fun lecture, I’ve found that most students are completely comfortable with this pace of presentation.

Then I ask my students which way they’d prefer: generating functions or mathematical induction? They usually respond induction. However, they also are able to realize that the thing that makes mathematical induction is also the challenge: they have to guess the correct formula and then use induction to verify that the formula actually works. On the other hand, with generating functions, there’s no need to guess the correct answer… you just follow the steps and see what comes out the other side.

Finally, to close the fun lecture, I tell them that the above steps can be used to find a closed-form expression for the Fibonacci sequence. (I devised the Quintanilla sequence for pedagogical purposes: since the denominator of its generating function easily factors, the subsequent steps aren’t too messy.) I won’t go through all the steps here, so I’ll leave it as a challenge for the reader to start with the generating function

f(x) = \displaystyle \frac{1}{1-x-x^2},

factor the denominator by finding the two real roots of 1 - x - x^2 = 0, and then mimicking the above steps. If you want to cheat, just use the following Google search to find the answer: http://www.google.com/#q=fibonacci+%22generating+function%22

green lineI conclude this post with some pedagogical reflections. I taught this fun lecture to about 10 different Precalculus classes, and it was a big hit each time. I think that my students were thoroughly engaged with the topic and liked seeing an unorthodox application of the various topics in Precalculus that they were learning (sequences, series, partial fractions, factoring polynomials over \mathbb{R}, mathematical induction). So even though they would likely receive a fuller treatment of generating functions in a future course like Discrete Mathematics, I liked giving them this little hint of what was lying out there for them in the future.

I covered the content of this series of five posts in a 50-minute lecture. I’d usually finish the proof by induction as time expired and then would challenge them to think about how to similarly find the formula for the Fibonacci sequence. The rules of a “fun lecture” were important to pull this off — I made it clear that students would not have to do this for homework, so the pressure was off them to understand the fine details during the lecture. Instead, the idea was for them to appreciate the big picture of how topics in Precalculus can be used in future courses.

Fun lecture on geometric series (Part 4): The Fibonacci sequence

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.

In this series of posts, I’m describing a fun lecture on generating functions that I’ve given to my Precalculus students. In the previous post, we looked at the famed Fibonacci sequence

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots

We also looked at that (slightly less famous) Quintanilla sequence

1, 1, 3, 5, 11, 21, 43, 85, \dots

which is defined so that each term is the sum of the previous term and twice the term that’s two back in the sequence. We also used the Bag of Tricks to find that the generating function is

Q(x) = \displaystyle \frac{1}{1-x-2x^2}

green lineTo get a closed-form definition of the Quintanilla sequence, let’s find the partial-fraction decomposition of Q(x). Notice that the denominator factors easily, so that

Q(x) = \displaystyle \frac{1}{(1+x)(1-2x)}

To find the partial fraction decomposition, we need to find the constants A and B so that

\displaystyle \frac{A}{1+x} + \frac{B}{1-2x} = \displaystyle \frac{1}{(1+x)(1-2x)},

or

A(1-2x) + B(1+x) = 1

Perhaps the easiest way of finding A and B is by substituting conveniently easy values of x.

  • If x = \displaystyle \frac{1}{2}, then we obtain \displaystyle \frac{3}{2} B = 1, or B = \displaystyle \frac{2}{3}.
  • If x = -1, then we obtain 3A =1, or A = \displaystyle \frac{1}{3}.

Therefore,

Q(x) = \displaystyle \frac{1}{3} \cdot \frac{1}{1+x} + \frac{2}{3} \cdot \frac{1}{1-2x}

green line

Finally, let’s write the rational functions on the right-hand side as infinite series. Using the formula for an infinite geometric series, we find

Q(x) = \displaystyle \frac{1}{3} \left(1 - x + x^2 - x^3 + x^4 - x^5 \dots \right) + \frac{2}{3} \left( 1 + 2x + 4x^2 + 8x^3 + 16x^4 + 32 x^5 \dots \right)

Notice that this matches the terms of the Quintanilla sequence! For example, the coefficient of the x^5 term is

\displaystyle -\frac{1}{3} + \frac{2}{3}(32) = \displaystyle \frac{63}{3} = 31,

which is a term of the Quintanilla sequence.

In general, the coefficient of the x^n term is

\displaystyle \frac{(-1)^n}{3} + \frac{2 \cdot 2^n}{3} = \displaystyle \frac{2^{n+1} + (-1)^n}{3}

This is the long-awaited closed-form expression for the Quintanilla sequence. For example, we quickly see that the 12th term is \displaystyle \frac{2^{13} + 1}{3} = 2731, which was obtained without knowing the 10th and 11th terms.

Fun lecture on geometric series (Part 3): The Fibonacci sequence

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.

In the two previous posts, I introduced the idea of a generating function and then talked about its application to counting money. In this post, we’ll take on the famous Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots

The Fibonacci sequence starts with two 1s, and each subsequent term is defined as the sum of the two previous terms. Of course, the generating function for this sequence is

f(x) = 1 + x + 2x + 3x^2 + 5x^3 + 8x^4 + 13x^5 + 21x^6 + 34x^7 + 55x^8 + \dots

green lineSlightly less famous than the Fibonacci sequence is (ahem) the Quintanilla sequence. It also begins with two 1s, but each subsequent term is defined as the sum of the previous term and twice the term that’s two back in the sequence. So,

  • The first term is 1
  • The second term is 1
  • The third term is 2(1) + 1 = 3
  • The fourth term is 2(1) + 3 = 5
  • The fifth term is 2(3) + 5 = 11
  • The sixth term is 2(5) + 11 = 21
  • The seventh term is 2(11) + 21 = 43
  • The eighth term is 2(21) + 43 = 85

And so on. The generating function for the Quintanilla sequence is

Q(x) = 1 + x + 3x^2 + 5x^3 + 11x^4 + 21x^5 + 43x^6 + 85x^7 + \dots

Both the Fibonacci and the Quintanilla sequences are examples of recursively defined sequences: we need to know the previous terms in order to get the next term. The major disadvantage of a recursively defined sequence is that, in order to get the 100th term, we need to know the 99th and 98th terms. To get the 98th term, we need the 96th and 97th terms. And so on. There’s no easy way to just plug in 100 to get the answer.

When I mention this to students, they naturally start trying to figure it out on their own. Occasionally, a student will notice that each term is roughly double the previous term. With a little more time, they see that the even terms are one less than double the previous term, while the odd terms are one more than the previous term. That’s entirely correct. However, that’s another example of a recursively defined function. So if a student volunteers this, I’ll use this as an opportunity to note that it’s pretty easy to find a recursive definition for a function, but it’s a lot harder to come up with a closed-form definition.

In order to get a closed-form definition for the sequence — something that we could just plug in 100 and get the answer — we will need to use the generating functions f(x) and Q(x).

green lineTo simplify the infinite series Q(x), we pull something out of the patented Bag of Tricks. In case you’ve forgotten, Socrates gave the Bag of Tricks to Plato, Plato gave it to Aristotle, it passed down the generations, my teacher taught the Bag of Tricks to me, and I teach it to my students.

Here’s the trick: let’s rewrite Q(x) and also figure out -xQ(x) and also -2x^2 Q(x):

Q(x) = 1 + x + 3x^2 + 5x^3 + 11x^4 + 21x^5 + 43x^6 + 85x^7 + \dots

-xQ(x) = \, \, \, -x- x^2 - 3x^3 - 5x^4 -11x^5 - 21x^6 - 43x^7 - \dots

-2x^2Q(x) = \, \, \, \, \, \, -2x^2 -2 x^3 - 6x^4 - 10x^5 - 22x^6 - 42x^7 - \dots

Let’s now add the last three green equations together. Notice that everything on the right-hand cancels except for 1! Therefore,

[1 - x - 2x^2] Q(x) = 1

Q(x) = \displaystyle \frac{1}{1-x-2x^2}

The generating function for the Fibonacci sequence is similarly found. You can probably guess it since the Fibonacci sequence does not involve doubling a previous term.

It turns out that these generating functions can be used to find a closed-form definition for both the Quintanilla sequence and the Fibonacci sequence. More on this tomorrow.

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

BugsBunny20cents

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.

green_speech_bubbleThere 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.

green lineUsing 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:

generating1Looking 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:

generating2Finally, 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.

generating3

green line

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/

Fun lecture on geometric series (Part 1): Generating functions

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 50-minute fun lecture — on the topic of generating functions — that I’ve given to my Precalculus students after they’ve learned about partial fractions and geometric series.

To launch the topic: 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

BugsBunny20cents

Notice that the price of candy from vending machines have increased somewhat since 1949. (Elsewhere in the cartoon, the price of a ticket to the movies was listed as 55 cents for adults, 20 cents for children, and 10 cents for rabbits.)

I wasn’t alive in 1949, but I vividly remember seeing this essentially mathematical problem while watching cartoons after school in the late 1970s. Now that I’m a little older — and can freeze-frame the above sign — I can see that the animators actually missed one way of expressing 20 cents. More on that later.

green line

Definition. The generating function of a sequence is defined to be an infinite series whose coefficients match the sequence.

Example #1. Consider the (boring) sequence 1, 1, 1, 1, \dots. The generating function for this sequence is

f(x) = 1 + 1x + 1x^2 + 1x^3 + \dots

If -1 < x < 1, then f(x) = \displaystyle \frac{1}{1-x}, using the formula for an infinite geometric series.

Example #2. For the slightly less boring sequence of 1, -1, 1, -1, \dots, the generating function is

f(x) = 1 - x + x^2 - x^3 + \dots,

which (if -1 < x < 1) is f(x) = \displaystyle \frac{1}{1+x}.

Example #3. Suppose a_n = \displaystyle {10 \choose n} if $0 \le n \le 10$ and a_n = 0 for n>10. Then the generating function is

f(x) = \displaystyle \sum_{n=0}^{10} {10 \choose n} x^n = (x+1)^{10}.

It turns out that the above problem from the Bugs Bunny cartoon can be viewed as a generating function. Let a_n denote the number of ways that n cents can be formed using pennies, nickels, dimes, and quarters? The Bugs Bunny cartoon is related to the value of a_{20}. What about one dollar? Two dollars? I’ll provide the answer in tomorrow’s post.

green line

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