My Students are People

Sometimes I forget that my students are people. Not like I treat them badly, or anything. That’s not what I mean. And I do try to think of them as more than only students. But there are times that I get so wrapped up in lesson planning and grading that I forget. Today I got reminded in two very striking ways that my students are not just math students.

First, we had advising conferences, and just looking at the schedules of my advisees jolted me back into reality. These students are taking a lot more classes than just math, and when I mentally think “why didn’t you just learn the material the night I presented it?”, I sometimes forget that these students are juggling with a lot of teachers all of whom are probably saying the same thing. Not that what we assign them is unmanagable. But it’s not an easy life for them. It’s much easier from our side of the teacher’s desk, looking through the spectacles on the edge of our noses, muttering “when I was your age…”

But it was hard for us then too. We just have had the luxury of forgetting.

Second, today was opening night for the school musical. It was HAIR and it was risque and long and clearly took a lot of preparation to stage. The students in it have worked their tails off to pull off another successful production. And a fair number of my students are involved with the musical. I was impressed by the amount of effort that the kids put into the production, yes, but it was also great to see students outside of the math room context. And outside of the hallway context. And in the theater. For many, the stage is their context, and I’m on their turf. It’s nice to see a student who generally struggles in my class get out on stage, grab the microphone, and belt out a tune.

My students are people.

We really do know it. We just need to remember not to forget it.

Generating Fibonacci: Part II

We left off in our quest for an explicit formula for the nth Fibonacci number having created this amazing generating function: $g(x)=\frac{1}{1-x-x^2}$ .

To do what we’re about to do, I need to remind you of two precalculus things:

First, that $\frac{1}{1-pq}=1+(pq)+(pq)^2+(pq)^3...$ . If you don’t know why, I suggest doing long division!

Second, partial fractions.

I’m going to go through this explanation assuming you know these two things.

So let’s look at the denominator of our $g(x)$ and factor it. Okay, okay, you got me. There isn’t a nice factoring with integers. But it can still be factored, of course.

$g(x)=\frac{1}{(1-x\phi)(1-x\overline{\phi})}$ , where $\phi=\frac{1+\sqrt{5}}{2}$ and $\overline{\phi}=\frac{1-\sqrt{5}}{2}$ . Using partial fractions, we get:

$g(x)=\frac{a}{1-x\phi}+\frac{b}{1-x\overline{\phi}}=a(\frac{1}{1-x\phi})+b(\frac{1}{1-x\overline{\phi}})$

We’ve made good headway, but what we don’t know are $a$ and $b$ ! However, noticing that we can use the first precalculus topic above, that

$g(x)=a(1+x\phi+x^2\phi^2+...)+b(1+x\overline{\phi}+x^2\overline{\phi}^2+...)$ .

Rewriting this as a simple polynomial, we get:

$g(x)=(a+b)+(a\phi+b\overline{\phi})x+(a\phi^2+b\overline{\phi}^2)x^2+...$

Now we’re almost done! We use the initial conditions to find out $a$ and $b$ .

Since we know $F_0=1$ and $F_1=1$ , we can say $a+b=1$ and $a\phi+b\overline{\phi}=1$ . Solving these two equations simultaneously yields $a=\frac{1}{\sqrt{5}}$ and $b=-\frac{1}{\sqrt{5}}$ .

So the nth Fibonacci number is: $\frac{1}{\sqrt{5}}(\phi^n)-\frac{1}{\sqrt{5}}(\overline{\phi}^n)$

which simplifies to: $\frac{1}{\sqrt{5}}(\phi^n-\overline{\phi}^n)$ .

Which is what we set out to show! Huzzah! What’s also nice about this (besides the fact that it’s an integer, which is surprising) is that it shows that the Fibonacci sequence grows exponentially!

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

My (Incorrect) Monday Math Madness Solution

This week’s Monday Math Madness was a bit of a brain strainer. I didn’t get the ideal solution, but hey, whatever. I still enjoyed working on it. The solution that I proposed is after the fold.

(more…)

I grow old, I grow old

I got an emergency email from a good friend from college (now in grad school at MIT) who is going to soon be meeting with a professor to talk about Number Theory (honestly, I have no idea why she needs to meet him; she does material science!).

She needs a crash course in it, and wanted a recommendation for a textbook. Of course, I go digging around online to find out what book I used, to no avail. I distinctly remember the cover, but I can’t find that on Amazon either. So I finally go to my last resort… digging through my 30 or so binders (from high school (!) and college) looking for the syllabus from that class.

I find the binder, but the syllabus doesn’t have the name of the textbook on it, even though it has 3 pages of assigned problems from the textbook.

My friend is, sadly, out of luck.

But here’s the horrible, horrifying part. Once I started looking through the old binder, I felt dumb. Like really, really dumb. For a number of reasons which I will enumerate here:

1. My three test scores (I don’t know what I got on the final) were 28/40, 29.5/40, and 32/40. [1]

2. One of the tests has a depressing, terse note from the professor “1 [point] for effort”

3. My class notes are completely beautiful but, for me today, totally incomprehensible. I mean, I don’t even remember most of the basic terms that I’m writing about.

Hensel’s Lemma: Let $f(x) \in Z[x]$ . $f(a) \equiv 0 \mod p^j$ , and $f'(a) \not\equiv 0 \mod p$ . Then there exists a unique $t \mod p$ such that $f(a+tp^j) \equiv 0 \mod p^{j+1}$ .

Did I ever understand that? Yeah, I know. If I had a month and the textbook, I would be able to figure out what that meant again. Which is (very) slightly heartening. But how sad it is that all my hard work in college is so fleeting? I wish it weren’t all so temporary.

PS. The subject line is from this poem.

[1] Okay, here I’m being a bit disingenuous. I remember that for at least one of them I scored the highest grade in the class. There were only 10-15 students in the class, and the teacher used to write up on the chalkboard the highest score, the lowest score, the mean, the median, the mode, and the standard deviation. Yikes. Those were scary moments, after the professor wrote that on the board, but before he returned the exams. But somehow, after teaching high school, scores in this form look bad. Even though they were probably fine. (I ended up with an A in the class.)

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!

To feel good, only to be dashed cruelly to the ground, and break in a million little pieces

The beautiful New York weather and three day weekend inspired to go out on this Saturday night. So I shaved, dollied myself up, donned my newly purchased tote bag, and left the apartment.

I felt pretty good about everything as I was having dinner with a friend, followed by a postprandial drink at a local coffeeshop. When I left, the barista on his cigarette break asked me if I was a designer. I, feeling good about how I put together my outfit, glowed, even though I played it cool. [1]

We made our way down three blocks to go to a concert at a local bar. The next person to speak to me was the bouncer, who looked me up and down. His first pronouncement arrived in question form: “Did you just get out of bed?”

[1] When I was in Paris, my friend Tom and I had our pictures taken by an aspiring fashion student for her work on “street fashion.” I felt good then too.

Continuous Everywhere but Differentiable Nowhere

I have no idea why I picked this blog name, but there's no turning back now