Engaging students: Using a recursively defined sequence

In my capstone class for future secondary math teachers, I ask my students to come up with ideas for engaging their students with different topics in the secondary mathematics curriculum. In other words, the point of the assignment was not to devise a full-blown lesson plan on this topic. Instead, I asked my students to think about three different ways of getting their students interested in the topic in the first place.

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission comes from my former student Enrique Alegria. His topic, from Precalculus: using a recursively defined sequence.

How can this topic be used in your students’ future courses in mathematics or science?

Recursion is heavily emphasized within the branches of computer science. The technique can be used more than just in arithmetic and geometric sequences for finding the next term. Within computer science, recursion techniques can be utilized for sorting algorithms. The content will be able to transfer easily. Instead of finding the previous term to use to find the current term, within sorting algorithms, a set of numbers is chunked into smaller and smaller sets such that the original set of numbers becomes sorted.

We can take a deeper look at Merge Sort which is a recursive sorting algorithm. What occurs is the set of numbers repeatedly gets cut in half until there is only one element in the list. From there the elements are sorted in increasing order. Traversing back into the original size of the list with all of the elements contained except the final output is the list in increasing order.

This image has an empty alt attribute; its file name is mergesort1.png

This image has an empty alt attribute; its file name is mergesort2.png

Students can inspect the algorithm visually and need not to understand the implementation of code to comprehend the functionality of recursion. Guiding the students towards the smallest part of the process which is the single element and from there rearranging the elements of the list.

How has this topic appeared in high culture (art, classical music, theatre, etc.)?

Recursively defined sequences influenced a renowned artist who is M.C. Escher. The concept of a sequence beginning at one point and continuing infinitely is how Escher exhibits recursion. Escher challenges the viewer of his work to determine the patterns from the artistic series.

This image has an empty alt attribute; its file name is drawinghands.png

For example, when observing the piece Drawing Hands, a student can predict what the ‘base case’ of the artwork would be followed by the next steps of the drawing. The spectator of this piece can break it apart into smaller and smaller partitions of the whole. And once they reach a starting point, they can put together the whole picture once again.

This image has an empty alt attribute; its file name is twobirds.png

Similarly, students can view this piece titled Two Birds to follow the patterns. Without saying the name of the piece students can again predict the base case and determine how recursion techniques would be used for this sequence. Students can begin to learn how to think of how recursively defined sequences are applied through visual representations of M.C. Escher’s artwork.

How can technology be used to effectively engage students with this topic?

Technology can be used to effectively engage students with recursion by showcasing the YouTube video “Recursion: The Music Videos of Michel Gondry” by Polyphonic. Through this video, students can compare recursively defined sequences to music they listen to. The video starts with singular notes and then repeating the notes to create a rhythm. Compiling the initial sounds into something familiar through loops of samples and sound bites. This video goes into the repetitive patterns of the small chunks of sound are shown through visual representations with the music videos by Michel Gondry. In the music video “Star Guitar” by The Chemical Brothers, the video starts off with the listener on a train ride going through a landscape. Slowly patterns emerge as buildings uniquely correspond to the notes and rhythms within the song. With this YouTube video students obtain a great introduction to recursion and hopefully continue to find patterns of recursion to music they listen to in the future.

References

Greenberg I., Xu D., Kumar D. (2013) Drawing with Recursion. In: Processing. Apress, Berkeley, CA. https://doi.org/10.1007/978-1-4302-4465-3_8

Miller, B., & Ranum, D. (2020). 6.11. The Merge Sort — Problem Solving with Algorithms and Data Structures. Runestone.academy. https://runestone.academy/runestone/books/published/pythonds/SortSearch/TheMergeSort.html.

https://www.youtube.com/watch?v=-rfezNHtwhg

Engaging students: Using sequences

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission comes from my former student Gary Sin. His topic, from Precalculus: using sequences.

How has this topic appeared in pop culture?

Probably the most used sequence in pop culture or art is the Fibonacci sequence. I learned about the Fibonacci sequence myself from “The Da Vinci Code” by Dan Brown. The Fibonacci sequence has been explored by many mathematicians over the years and if we divided 2 successive numbers (larger divided by the smaller), the limit of the ratio is the golden ratio.

The golden ratio was heavily believed to be seen in nature itself. Naturally people were fascinated that such a number could be seen everywhere in nature. Many artists based their art on the golden ratio, believing that the ratio is aesthetically pleasing. A great example is the polyhedral seen in “’The Sacrament of the Last Supper” by Salvador Dali. Modern architects also utilize the golden ratio in their builds. It was also believed that the proportions of the different parts of the limbs of humans are in the golden ratio.

The Fibonacci Sequence is fascinating and is a great way to demonstrate to students the beauty in math and how even artists are influenced by it and is a beautiful link to how mathematics can also be seen in nature.

How could you as a teacher create an activity or project that involves your topic?

Sequences are fun to play around with as some sequences are infinite or finite and the series they form could converge to a number. Students could be given a starting sequence and are asked to find the nth term of a sequence. I could also point out how sequences can be seen in something as simple as the list of natural numbers, multiples of positive integers.

Students could also be given both arithmetic and geometric sequences and plot them on a graph accordingly to see if the sequence progresses linearly or exponentially. I could also introduce sequences that are neither and that are divergent.

One of the important usefulness of sequences is how it relates to limits of a sequence. I could provide a fun riddle for students to figure out the limit of a sequence using word problems like Zeno’s Paradox. Students can figure out the rule of a sequence and plot it on the graph to see how it converges toward a number.

How does this topic extend what your students’ should have learned in previous courses?

The most amazing thing about sequences is that students use them from the moment they learn how to count as kids. Natural numbers are sequences that are obtained by adding 1 to the previous term. Naturally, the multiples of positive integers are also sequences. Students will also realize that the powers of a base are geometric sequences. When learning about plotting functions, linear, quadratic or cubic; the students are basically using sequences and basic pattern recognition to create tables of values and observing the rate of change.

Sequences are especially important in bridging a simple concept like a sequence to limits of functions, limits of infinity are an important abstract idea that provokes the students to think more about how a function would act if it kept going forever.

When determining a recursive of exclusive formula for sequences, students will also have to apply basic algebra, order of operations, arithmetic, exponents in order to create or prove that a formula works for a sequence.

Engaging students: Using a recursively defined sequence

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission comes from my former student Austin DeLoach. His topic, from Precalculus: using a recursively defined sequence.

How could you as a teacher create an activity or project that involves your topic?
One activity that would be interesting to introduce recursion would be Fibonacci’s rabbit problem. In his book, Liber Abaci, Fibonacci introduced a problem where you start with one young pair of rabbits and try to find out how many rabbits you would have after a year. Every month, a grown pair of rabbits can give birth to a new pair, and it only takes one month for a young pair to grow up and be able to reproduce on their own, and the rabbits also never die. This is one of the most popular recursive sequences (the Fibonacci sequence), and, by itself, can be solved without a prior knowledge of recursion, but is a very good way to introduce the idea once the students begin to analyze the pattern of how many pairs of rabbits there are after each month. This problem is laid out in this video, https://youtu.be/sjQlW6cH3Ko but it is not necessary to show the video to introduce the problem.

How can this topic be used in your students’ future courses in mathematics or science?

One major place that a solid grasp of recursion can be used is in computer programming courses. Although not everyone takes these, they are becoming increasingly popular and the field is not likely to shrink any time soon. In programming, there are certain things that can either only be written recursively (as opposed to explicitly) or at least ones that are simpler to write and understand with recursion than with an explicit algorithm. There are also times, depending on the language and content, that a recursive function can be more efficient. Because of this, an understanding of recursion is becoming increasingly important for more people, and the ability to write and understand how it works is practically becoming necessary. So, even though not every student will go on to take computer science, many will, and the basic idea is still important to understand.

How can technology be used to effectively engage students with this topic?

There is a series of Khan Academy videos on recursively defined sequences online. The first one is https://youtu.be/lBtb30SjU2Q and it shows how to read and understand what the basic frame for recursion is. Although Khan Academy videos are not always the most engaging for all students, they do work for many because of their consistent structure. This video in particular is about recursive formulas for arithmetic sequences. Without mentioning the vocabulary yet, the video does introduce the idea of a base case and the method for finding subsequent values. The video both shows how to look at a list of values and determine the recursive definition, as well as how to understand the recursive definition if that is what you are given. For a three minute video, it does a very good job of introducing important topics for recursive series and explaining the basic ideas so that students have a framework to build on later when more complex recursively defined sequences are introduced.

References:
1. https://youtu.be/sjQlW6cH3Ko
2. https://youtu.be/lBtb30SjU2Q
3. https://plato.stanford.edu/entries/recursive-functions/

My Favorite One-Liners: Part 28

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them. Today’s quip is one that I’ll use when simple techniques get used in a complicated way.

Consider the solution of the linear recurrence relation

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

where $F_0 = 1$ and $F_1 = 1$ . With no modesty, I call this one the Quintanilla sequence when I teach my students — the forgotten little brother of the Fibonacci sequence.

To find the solution of this linear recurrence relation, the standard technique — which is a pretty long procedure — is to first solve the characteristic equation, from $Q_n - Q_{n-1} - 2 Q_{n-2} = 0$ , we obtain the characteristic equation

$r^2 - r - 2 = 0$

This can be solved by any standard technique at a student’s disposal. If necessary, the quadratic equation can be used. However, for this one, the left-hand side simply factors:

$(r-2)(r+1) = 0$

$r=2 \qquad \hbox{or} \qquad r = -1$

(Indeed, I “developed” the Quintanilla equation on purpose, for pedagogical reasons, because its characteristic equation has two fairly simple roots — unlike the characteristic equation for the Fibonacci sequence.)

From these two roots, we can write down the general solution for the linear recurrence relation:

$Q_n = \alpha_1 \times 2^n + \alpha_2 \times (-1)^n$ ,

where $\alpha_1$ and $\alpha_2$ are constants to be determined. To find these constants, we plug in $n =0$ :

$Q_0 = \alpha_1 \times 2^0 + \alpha_2 \times (-1)^0$ .

To find these constants, we plug in $n =0$ :

$Q_0 = \alpha_1 \times 2^0 + \alpha_2 \times (-1)^0$ .

We then plug in $n =1$ :

$Q_1 = \alpha_1 \times 2^1 + \alpha_2 \times (-1)^1$ .

Using the initial conditions gives

$1 = \alpha_1 + \alpha_2$

$1 = 2 \alpha_1 - \alpha_2$

This is a system of two equations in two unknowns, which can then be solved using any standard technique at the student’s disposal. Students should quickly find that $\alpha_1 = 2/3$ and $\alpha_2 = 1/3$ , so that

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

which is the final answer.

Although this is a long procedure, the key steps are actually first taught in Algebra I: solving a quadratic equation and solving a system of two linear equations in two unknowns. So here’s my one-liner to describe this procedure:

This is just an algebra problem on steroids.

Yes, it’s only high school algebra, but used in a creative way that isn’t ordinarily taught when students first learn algebra.

I’ll use this “on steroids” line in any class when a simple technique is used in an unusual — and usually laborious — way to solve a new problem at the post-secondary level.

Fibonacci convention

Source: https://www.facebook.com/Mathhappiness/photos/a.170688796611683.1073741829.101136273566936/321994341481127/?type=3&theater

Furbonacci Sequence Proves That Cats Are Purrfect

Source: http://www.boredpanda.com/fibonacci-composition-cats-furbonacci/

Engaging students: Fibonacci sequence

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission comes from my former student Taylor Vaughn. Her topic, from Precalculus: the Fibonacci sequence.

How has this topic appeared in pop culture (movies, TV, current music, video games, etc.)?
The article “Music and the Fibonacci sequence and Phi” talks about how the Fibonacci sequence correlates how the keys on the piano are laid out. Also talks about how the sequence also affects the frequency of chords. One thing I like about this article is that it doesn’t just talk about the sequence in one way, like how the instrument is made, but also different aspects like the chord. In other showings of the Fibonacci sequence they talk about pine cones and flowers. Personally, I think that music is something that is more relatable to students and a lot of people have seen a piano, but never just thought about the making. People who are that involved in music, probably noticed that there was some pattern to the keys, but didn’t think that by any chance that it was related to math.

What interesting things can you say about the people who contributed to the discovery and/or the development of this topic?
Since the sequence is named Fibonacci sequence you may think that the founder’s name is Fibonacci, but actually his name is Leonardo of Pisa. The nickname Fibonacci comes from the shortening of the Latin term “filius Bonacci”, which means son of Bonacci. Well why does that matter? That was his dad’s last name. Also, the Latin phrase is incorporated in the title of his book. One thing that I found cool, was that Leonardo actually had a North African education. When talking about mathematicians you never hear anything about Africa. So let’s look at the history of the sequence itself. After reading a few articles, some believe that he actually didn’t discover the sequence himself, but merely saw it during his travels and he was the one to actually write about it. Edouard Lucas is the person who named the sequence, the Fibonacci sequence. When Fibonacci wrote about the sequence it was in the 1200’s, Lucas wasn’t around until the 1800’s. That is 600 years that the sequence didn’t have a name. So during that time, what did people refer to it as? I really don’t know. Lucas is the person to look more into the sequence and noticed that the numbers have a common ratio, which is now called the golden ratio, he also discovered other patterns that lie in the sequence.

How can technology (YouTube, Khan Academy [khanacademy.org], Vi Hart, Geometers Sketchpad, graphing calculators, etc.) be used to effectively engage students with this topic?
The video Doodling in Math: Spirals, Fibonacci, and Being a Plant [1 of 3] was an engaging video because it actually shows the sequence in different objects. For example, when she talks about the sequence in pine cones she actually gets glitter paint, and shows and counts the diagonals on the pine cone. Also I like that she uses pine cones of different sizes and shapes, and shows that the pattern still holds s that students don’t think that it was planned that she picked up that type of pine cone. I also like that she brings in relevant object like fruit. I think this is a good engage because it shows patterns of things that students see often, but never stopped and paused to think about. One thing I don’t like about Vi Hart is the speed that she talks. I normally have to watch the video multiple times to get all the information she gives. In a classroom, you really don’t have the time to allow students to watch the video multiple times. This video could also be given as homework before their lesson and it would allow students to watch it multiple times and could turn in their notes, or provide questions for them to answer. I definitely think that the video is cool and would spike some interest in entering sequences.

Citations
Meisner, Gary. “Music and the Fibonacci Sequence and Phi – The Golden Ratio: Phi, 1.618.” The Golden Ratio Phi 1618. N.p., 04 May 2012. Web. 15 Nov. 2015.
Knott, Dr. Ron. “Contents of This Page.” Who Was Fibonacci? Ron Knott, 11 Mar. 1998. Web. 15 Nov. 2015.
Knott, Ron, and The Plus Team. “The Life and Numbers of Fibonacci.” The Life and Numbers of Fibonacci. N.p., 4 Nov. 2013. Web. 15 Nov. 2015.
Hart, Vi. “Doodling in Math: Spirals, Fibonacci, and Being a Plant [1 of 3].” YouTube. YouTube, 21 Dec. 2011. Web. 15 Nov. 2015.

Formulas for arithmetic and geometric sequences (Part 1)

I’m not particularly a fan of memorizing formulas. Apparently, most college students aren’t fans either, because they often don’t have immediate recall of certain formulas from high school when they’re needed in the collegiate curriculum.

While I’m not a fan of making students memorize formulas, I am a fan of teaching students how to derive formulas. Speaking for myself, if I ever need to use a formula that I know exists but have long since forgotten, the ability to derive the formula allows me to get it again.

Which leads me to today’s post: the derivation of the formulas for the $n$ th term of an arithmetic sequence and of a geometric sequence. This topic is commonly taught in Precalculus but, in my experience, is often forgotten by students years later when needed in later classes.

An arithmetic sequence is specified by two numbers: the first term and the common difference between terms. For example, if the first term is $16$ and the common difference is $3$ , then the sequence begins as

$16, 19, 22, 25, 28, 31, 34, \dots$

If the first term is $29$ and the common difference is $-4$ , then the sequence begins as

$29, 25, 21, 17, 13, 9, 5, 1, -3, \dots$

For those of us old enough to remember, our favorite arithmetic sequences came from Schoolhouse Rock:

Let’s discuss the first arithmetic sequence, whose first seven terms are:

$16, 19, 22, 25, 28, 31, 34, \dots$

How do we get the $8$ th term? That’s easy: we just add $3$ to $34$ to get $37$ .

How to we get the $100$ th term. That’s easy: we just add $3$ to the $99$ th term.

Oops. We don’t know the $99$ th term. To get the $99th$ term, we need the $98$ th term, which in turn requires the $97$ th term. Et cetera, et cetera, et cetera.

The trouble (so far) is that an arithmetic sequence is recursively defined: to get one term, I add something to the previous term. Mathematically, the arithmetic sequence is defined by

$a_n = a_{n-1} + d$ ,

where $d$ is the common difference. This can be very intimidating to students when seeing it for the first time. So, to make this formula less intimidating, I usually read this equation as “Each next term in the sequence is equal to the previous term in the sequence plus the common difference.”

It would be far better to have a closed-form formula, where I could just plug in $100$ to get the $100$ th term, without first figuring out the previous $99$ terms.

To this end, we notice the following pattern:

Second term: $19 = 16 + 3$
Third term: $22 = 19 + 3 = 16 + 3 + 3 = 16 + 2 \times 3$
Fourth term: $25 = 22+ 3 = 16 + (2 \times 3) + 3 = 16 + 3 \times 3$
Fifth term: $28 = 25+ 3 = 16 + (3 \times 3) + 3 = 16 + 4 \times 3$
Sixth term: $31 = 28+ 3 = 16+ (4 \times 3) + 3 = 16 + 5 \times 3$
Seventh term: $34 = 31 + 3 = 16 + (5 \times 3) + 3 = 16 + 6 \times 3$

It looks like we have a pattern, so we can guess that:

One hundredth term = $16 + (100-1) \times 3 = 313$

In general, we have justified the closed-form formula

$a_n = a_1 + (n-1)d$ ,

where $a_1$ is the first term, and $d$ is the common difference. In words: to get the $n$ th term of an arithmetic sequence, we add $d$ to the first term $n-1$ times. (This may be formally proven using mathematical induction, though I won’t do so here.)

A closed-form formula for a geometric sequence is similarly obtained. In a geometric sequence, each term is equal to the previous term multiplied by a common ratio. Mathematically, the geometric sequence is recursively defined by

$a_n = a_{n-1}r$ ,

where $r$ is the common ratio. For example, if the first term is $3$ and the common ratio is $2$ , then the first few terms of the sequence are

$3, 6, 12, 24, 48, dots$

By the same logic used above, to get the $n$ th term of an geometric sequence, we multiply $r$ to the first term $n-1$ times. Thus justifies the formula

$a_n = a_1 r^{n-1}$ ,

which may be formally proven using mathematical induction.