Good Math Problems

Generating Fibonacci: Part I

Yes, this is a YAFPOTW (Yet Another Fibonacci Post On The Web).

People have talked about and analyzed the Fibonacci sequence to death. So I’m clearly not going to be doing something new and novel for everyone. But I remember one stunning way to look at Fibonacci is through Generating Functions. You only really need precalculus to understand it, as long as you allow for infinite degree polynomials. And the best part is: you can apply this method to any simple recurrence relation.

To refresh your memory, the Fibonacci sequence is: 1,1,2,3,5,8,13,…, where the nth Fibonacci number is the sum of the two preceeding Fibonacci numbers:

F_n=F_{n-1}+F_{n-2}.

That recursive formula, with the initial conditions (F_0=1 and F_1=1), defines the entire sequence.

Let’s create a polynomial function from these Fibonacci numbers:

g(x)=F_0+F_1x+F_2x^2+...+F_{n-2}x^{n-2}+F_{n-1}x^{n-1}+...

We call this function g(x) the generating function of the sequence F_0, F_1, F_2,....

So what if we add g(x)+xg(x)? First we find xg(x):

xg(x)=F_0x+F_1x^2+F_2x^3+...+F_{n-3}x^{n-2}+F_{n-2}x^{n-1}+...

and we add, term by term, to get:

g(x)+xg(x)=F_0+(F_0+F_1)x+(F_1+F_2)x^2+...+(F_{n-3}+F_{n-2})x^{n-2}+...

Excellent! Do you see where this is going? HUZZAH We know those coefficients! They use the recursion formula that defines the Fibonacci numbers! So we simplify:

g(x)+xg(x)=F_0+F_2x+F_3x^2+...+F_{n-1}x^{n-2}+...

And we know F_0=1=F_1, we replace that F_0 above to get:

g(x)+xg(x)=F_1+F_2x+F_3x^2+...+F_{n-1}x^{n-2}+...

Notice the right side of the equation is equal to:

\frac{1}{x}[-F_0+F_0+F_1x+F_2x^2+F_3x^3+...+F_nx^n+...]

which immediately shows us a g(x)! So we can rewrite that to as the much simpler:

g(x)+xg(x)=\frac{1}{x}[-F_0+g(x)]

And we’re almost there! Replacing F_0 with it’s value of 1, multiplying both sides by x, and rearranging, yields: (x^2+x-1)g(x)=-1. So we get:

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

This is our generating function! The coefficients of the polynomial expansion will give you the Fibonacci sequence! But this method of generating functions will prove a nice and general way to find explicit solutions for any basic recursive relation. (What if we had the Lucas Numbers, for example? Or some recurrence like M_n=2M_{n-1}+M_{n-3}?)

In a later post, I’ll write about how to get an explicit formula for the nth Fibonacci number from this. In case you need a refresher or never knew:

F_n=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)

Where clearly we see some popping up of the golden ratio and its “opposite”! And in our generating function, we see an 1-x-x^2 which has zeros which are the golden ratio and its “opposite.”

At the last Math Club meeting…

At the last meeting of Math Club, one of the members presented the solution to a problem he posed the week before.

There is a prison with 100 prisoners. They are all taken into a room and the warden says:

“In the room next to this one, there are 100 boxes in a row. Each of these boxes contains a slip of paper in it, and on these 100 slips of paper are your names. You may strategize as much as you’d like now, but once you have a strategy, you are each going to be sequestered in individual cells. One by one, you will be led to the room with the boxes, and you will get to open only 50 boxes in an attempt to find your name. Then you leave all room, with all the boxes exactly as you found them. You cannot change anything; you cannot take a slip from the boxes, not even your own. Then go you back to being sequestered, and the next prisoner will be led to the room. At the end, after all 100 of you have had your chance, you must tell me which box has your name in it. If all of you get your box right, then you all can leave the prison. If any of you get your box wrong, none of you can leave.”

What is the best strategy for the prisoners?

The dumb “every prisoner randomly picks 50 boxes” method will give them a chance of \frac{1}{2^{100}}. You can beat that. In fact, the prisoners can come up with a strategy that will give them a pretty good chance of leaving. Not 100% (obviously), but pretty good.

And in fact, I had no idea where to even begin. But it turns out that another mathclubber came up with the right strategy. Which is awesome!

UPDATE: If you want the solution, it’s well explained on this blog post. Saves me the time of typing out the answer!

When I’m busy, tired, stressed, I turn to math

This has been a stressful few days. In my school, we have to write comments on each student (about 1/2 page single spaced) and those are due on Thursday. In addition, with the end of the third quarter, there has been a massive grading effort on my part to finish up the video projects I assigned. Plus, that hiring committee I was on took a ton of my time.

Still, even though I have bloodshot eyes and am crashing at random times during the day and evening, I couldn’t help but get addicted to working on Blinkdagger’s Monday Math Madness problem. I think I found a solution, but the great (and cruel) thing about optimization problems is that you can’t check to see if you have the best solution without proving that no other method will beat the method you came up with. Which I’m not going to do. But not knowing if I have the optimal solution is frustrating, but also exciting, because it’s a different experience to not know with certainty if I’ve finished the problem right or not.

I have to say that this problem, more than any other problem I’ve encountered in recent memory, has gotten my brain to work in such a different and crazy way that I have to recommend it to everyone. I think those in computer science (read: not me) will find it easier than I did.

With that said, the hardest part of this wasn’t actually coming up with my solution, but it was writing it in a way that could be understood by someone else. I wanted a student from, say, my high school math club to be able to follow the logic. But whether I succeeded or not, that’s a question that will have to wait until the contest is over and I post my solution.

With that said: check out the problem, test your mathematical mental mettle.

Spinning on a Globe

This slideshow is the Smartboard I used in this class that I describe below:

The day my students got back from spring break, this week, I started things off with a bang! At least, that was the intention. Instead of doing the whole “Paris was great, where did you go for your vacation?” time waster, I decided to dive right in. They left for break having learned some trigonometry basics, and I had blown their minds with the idea that you can measure angles with something other than degrees (radians). Monday’s lesson was to be on central angles, arcs, and angular velocity.

On Sunday night, I downloaded GoogleEarth onto my school laptop. In an ideal world, I wanted to say:

So kiddos, I flew from Newark to Paris for spring break. Let’s all get out our laptops and find out their longitude and latitude, and the distance between them. [I do it in front of them on GoogleEarth]. Now let’s use this info to the find the radius of the earth.

Unfortunately, after a few minutes of playing around with this problem, it becomes very clear to me that it is not as simplistic and trivial as I had hoped, because the latitude and longitude are different. Picture the following. Draw a line from the center of the earth to Newark, from the center of the earth to Paris, and a curved line (along the globe) from Newark to Paris. You have a sector of a circle. You know the arc length. But what’s the central angle (the angle between the radii)? It’s not a trivial problem for students to calculate that angle.

So instead, I copped out and found two random spots on the equator (one in Brazil, one in the Democratic Republic of Congo), and the distance between them. And then I had students come up with what to do next. It took very little time before they stumbled upon the idea of setting up a proportion: angle/full circle angles = arc/full circle perimeter.

\frac{87.74}{360}=\frac{9610.10 km}{Circumference}

From that, we found the circumference of the globe (about 40,046km). And then we compared it to what Wikipedia said (40,075km), marveled at our own acumen, and talked about the sources of error. And because I truly am a big nerd, I talked about the origin of the meter (see this book).

This warmup took about 10 minutes, and was a perfect segway into a discussion of arc length and central angles.

We set up the same proportion as we did above, but for a general circle of radius r, central angle \theta, and arc length s, to discover the wonderful formula s=r\theta. Then I asked them if it made sense… (The larger the circle’s radius, the larger the arc length… check! The smaller the angle, the smaller the arc length… check!) And when I asked them when they had seen this before, most of my students noticed: “duh Mr. Shah, the Earth problem…”[1]

Finally, I got to the final topic, angular speed. I remember when I was first taught this, I was taught it as a formula. There was no conceptual understanding behind it. And students tend to love to rely on formulas without understanding them. So I introduced the ideas of “linear speed” and “angular speed” — and then asked them to calculate (without showing them any problems) the linear speed and angular speed of someone in Brazil or the Democratic Republic of Congo as the earth spun on it’s axis. And someone’s hand shot in the air, then another, and soon the problem was solved.

In addition, one student noticed that the angular velocity remained the same no matter where on the globe you stood, but your linear velocity decreased the further away you got from the equator.

Which led to the final equation of the day: v=r\omega.

Some more practice problems were done, and that was that. With that concluded one of my better, more cohesive lessons. It all tied together with the globe thing, and they really left with a sense of the concepts, more than the simply memorizing the formulas.

[1] One class noticed we could calculate the radius of the earth with this formula, since in our earlier problem, we knew the distance between the places in Brazil and the Democratic Republic of Congo, and the angle between them… So we did that, and got another wonderfully accurate answer too!

I lost, but it’s the journey that matters.

So I didn’t *win* Monday Math Madness. For those of you not in the know, the blog WildAboutMath is having a rotating math problem contest with another website, and I put my hat in the ring. And I got the answer right. Sadly, the random number generator did not love me (click link for a few different solutions).

This week’s problem was:

A popular blog has just three categories: brilliant, insightful, and clever. Every blog post belongs to exactly one of the three categories and the category for each post is selected at random. What is the probability of reading at least one post from each category if a reader reads exactly five posts?

After solving it, I tried thinking of natural extensions. Clearly, one is: “if you have p posts and n tags: what is the probability that a reader reads at least one post from each category if a reader reads exactly p posts?” Or one could think about the more difficult question, where the frequency of each tag is different (not equal chance of stumbling across each post).

My submitted solution after the fold. You can see how hard it is to explain math clearly in an email.

(more…)