Monday, July 11, 2011

Sequences Part II – The Future is in the Past

In Sequences Part I, we talked about what a sequence is, and then we talked about straight up sequences. If you need a refresher, just visit the post by clicking here.

Today, we’re going to talk about recursive functions for sequences. That is, ones that look like this: clip_image002

This is a recursive sequenceor one that uses previous terms to define the next term. This particular sequences is called the Fibonacci Sequence. Mostly it’s just a regular sequence that gets a special name because it’s pretty important to mathematics – but we won’t really get in to much of that in this post.

Remember the cups we talked about? Let’s go back to those and see if we can figure out the Fibonacci sequence. Now, the thing about recursive sequences is that you usually have to take at least one of the cups before the cup you’re working on, and use those numbers in your function. Let’s just take a look at it.

cupsWith this recursive sequence, we have the first two terms defined for us.

clip_image002[1]

dumpingcups

So, now that we have our first two cups filled up, we can start with our second cup, which would be clip_image002[3]. The sequence says clip_image002, so basically what that means is that we fill up each cup with everything that was in the last two cups (because we’re adding – and adding is just like putting things together in a mixing bowl when you’re cooking).

So if n=2 (clip_image002[3]), then that means we need to take clip_image002[6] and clip_image002[8] (or the two cups right before cup “2”) and dump them into clip_image002[3]‘s cup. clip_image002[6]=1 and clip_image002[8]=1, so when you dump those into a cup, you get 2, right? So clip_image002[3]=2. (I’ve made some illustrations for what’s happening.

dumpingcups2          dumpingcups3 

Now for the third cup, clip_image002[10], we dump in the last two cups, which are now cups 1 and 2. clip_image002[8]=1, and clip_image002[3]=2, so clip_image002[10]= 2 + 1 = 3. At first the Fibonacci sequences just looks like clip_image002[12], but let’s just keep going. dumpingcups4

We need cups “3” and “2” to fill up cup “4”. clip_image002[3]= 2, and clip_image002[10]= 3, so when we dump in those two cups we get clip_image002[14]= 3 + 2 = 5, so clip_image002[14]=5, and now we don’t have clip_image002[12] - we have Fibonacci!

When you write it out, it’s pretty easy to see what the next term will be:

clip_image002[16]

Now I’m going to give you a few practice problems. I’ll post the answers tomorrow, to give you a chance to figure them out on your own.

Find the first 5 terms of each sequence.
(write your answers in the comment section, or email them, or post them on Twitter or Facebook. Those who come up with the correct answers before I post them tomorrow will be mentioned in the answers post)

1. clip_image002[18]

2.clip_image002[20]


3.clip_image002[22]

4.clip_image002[24]


5.clip_image002[26]

If you have questions, you can ask them in the comments, email me, ask on Facebook, or on Twitter. I am on Facebook and Twitter live from 3:00-3:30 pm Mon-Thurs MDT.

No comments:

Post a Comment