Whiteboard

4
Aug/091

Generating Functions

''A generating function is a clothesline on which we hang up a sequence of numbers for display.''

—Herbert Wilf, (Generatingfunctionology)

The Canonical Example: Fibonacci

Say I have two rabbits. Bunnies, if you will. And I let them reproduce as quickly as possible. The gestation period for bunnies is about a month, and, as usual, for the purposes of math we'll disregard the consequences of incest. We'll also assume all bunnies live only two months (procreating twice), mostly because we really like hasenpfeffer. Lastly, we assume all litters are of size two (one male, one female), even though in reality they are usually six, which we do for no reason other than tradition, since we could ultimately use the same method if we assumed six.

Let's see what these assumptions lead to. For the sake of numbering let's say we acquire the first pair at the end of the first month (one month waiting period on bunnies in some states). In the second month, the first pair begets a new pair (and we name them Helena Cain and Niels Henrik Abel), so we have two pairs. In the third month, each of the two pairs begets a new pair, and the first pair dies, so we have three pairs. Month four: three new pairs, one pair dies, totaling five pairs. We let this process go until all available biomass is converted into bunnies.

bunnies

What we see along the way is that, at the end of any particular month, the total number of bunnies we have is the number of newborn bunnies (which is equal to the number we had at the start of last month) plus the number of one-month-old bunnies, which is equal to the number of newborns at the beginning of last month, and by the same logic as before, this is equal to the number of bunnies we had at the start of the month before that, or the number of bunnies from two months ago. To summarize, the number of bunnies this month is equal to the number of bunnies last month plus the number of bunnies from two months ago, which we write as

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

Now we want to solve for $F_n$ in terms of $n$ , so that if someone asks us how many there will be in 5 years (60 months), instead of working out how many there were in month one and two, and then adding to get the number for month three, and repeating this process 57 more times, we can just substitute 60 for n in some expression and get the answer. One technique is to look at the following table and try to guess what $F_n$ is in terms of $n$ :

$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline n&0&1&2&3&4&5&6&7&8&9&10&\cdots&60\\\hline F_n&0&1&1&2&3&5&8&13&21&34&55&\cdots&?\\\hline\end{array}$

A better technique is to use a generating function, which is a polynomial made out of a sequence. As is typical in math, you won't see why we make up this idea of a generating function until everything comes together, the answer pops out, and the magician shows you how his trick worked. You have to play along and see the trick in action first.

So to reiterate we have a sequence of numbers $F_0, F_1, F_2, F_3, F_4,\ldots$ that we want to figure out, and all we know is that $F_0 = 0$ , $F_1=1$ , and in general $F_n = F_{n-1} + F_{n-2}$ . The generating function for this sequence is the following polynomial:

$f(x) = F_0 + F_1 x + F_2 x^2 + F_3 x^3 + F_4 x^4 + \cdots$

This can be written more compactly as

$f(x) = \sum_{n=0}^\infty\limits F_n x^n$ ,

which means take the sum of terms of the form $F_n x^n$ where we first replace $n$ by 0, then 1, and on to infinity. Now we do some algebra with sums:

$\begin{array}{rclr}f(x)&=&\sum_{n=0}^\infty\limits F_n x^n&\\&=& F_0+F_1x+\sum_{n=2}^\infty\limits F_nx^n&\text{expand the sum}\\&=& F_0 + F_1x + \sum_{n=2}^\infty\limits \left( F_{n-1} + F_{n-2} \right) x^n&\text{use }F_n = F_{n-1} + F_{n-2}\\ &=&0+1 x + \sum_{n=2}^{\infty}\limits F_{n-1}x^n + \sum_{n=2}^{\infty}\limits F_{n-2}x^n&\text{use }F_0=0\text{ \& }F_1=1\\ &=& x + x\sum_{n=0}^{\infty}\limits F_nx^n + x^2\sum_{n=0}^{\infty}\limits F_nx^n&\text{reindex the sums }\\ &=& x + x f(x) + x^2 f(x)&\end{array}.$

(One might want to work through the reindexing step above if they haven't seen it before, as it's a common trick.) Finally we solve for $f(x)$ in the last equation above to get that

$f(x)=\dfrac{x}{1-x-x^2}$ .

If we can rewrite the right side as a sum, the coefficients will be the sequence we want. To do this we first need to factor $1-x-x^2$ , which we do by finding both of its roots (since it's quadratic, we use the quadratic formula to do this). We end up with

$1-x-x^2=-(x+\phi)(x+\phi')$ ,

where $\phi=\frac{1+\sqrt{5}}{2}\approx 1.618$ (which is the golden ratio) and $\phi'=\frac{1-\sqrt{5}}{2}\approx -0.618$ . We use partial fraction decomposition to find that

$f(x)=\dfrac{x}{-(x+\phi)(x+\phi')}=\dfrac{1}{\sqrt{5}}\left(\dfrac{\phi'}{x+\phi'}-\dfrac{\phi}{x+\phi}\right)$ .

We simplify this using the fact that $\phi=-1/\phi'$ to get

$f(x)=\dfrac{1}{\sqrt{5}}\left(\dfrac{1}{1-\phi x}-\dfrac{1}{1-\phi' x}\right)$ ,

and finally we use the formula for geometric series to write

$\dfrac{1}{1-\phi x}=\sum_{n=0}^\infty\limits\phi^n x^n\qquad\text{ and }\qquad\dfrac{1}{1-\phi' x}=\sum_{n=0}^\infty\limits\phi'^n x^n$ .

Putting this all together, we get the solution (called Binet's Formula):

$f(x)=\sum_{n=0}^\infty\limits\dfrac{\phi^n-\phi'^n}{\sqrt{5}}\ x^n\quad\text{ and }\quad f(x)=\sum_{n=0}^\infty\limits F_n x^n \quad\Longrightarrow\quad F_n=\dfrac{\phi^n-\phi'^n}{\sqrt{5}}.$

Therefore, after 5 years, we should have

$F_{60}=\dfrac{1.618^{60}-(-0.618)^{60}}{2.236}$

or about 1.5 trillion pairs of rabbits.

The General Method

In general, whenever we have a linear recurrence relation, which defines each number of a sequence according to some linear combination of the previous terms, we can use a generating function to get an expression just in terms of $n$ and some constants. In the above example, the linear recurrence relation was $F_n = F_{n-1} + F_{n-2}$ , but we could use similar techniques to solve something like $F_n = 6F_{n-1}+F_{n-2}+77 F_{n-4}+4^n$ (although since it's non-homogeneous, i.e. it has that $4^n$ term, it requires a little more work).

There are also nonlinear recurrence relations, some of which are quite useful in science, such as $F_n=r F_{n-1}(1-F_{n-1})$ , called the logistic map, which is studied in chaos theory and can be used to predict the populations of various species.

Chaotic behavior based on the r parameter

Chaotic behavior of the logistic map based on the r parameter

Tagged as: mathematics

1 Comment

26
Aug/070

Japan internship update

"...studying Oriental ideas not in the spirit of saying to the West, 'You ought to be converted to Oriental ideas,' but in the spirit of saying, 'You don't understand the basic assumptions of your own culture if your own culture is the only culture you know.'"

--Alan Watts

I'll start off with the last event from last night, and from there I'll continue from where I previously left off and connect the two points.

For a while, when asked what I would be doing this summer, I replied that I would be modeling in Tokyo. And from there I clarified that I'd be mathematically modeling polymers for a chemical company near Tokyo.

It seems that life didn't find my little joke very funny and decided to trump it.

Last night I was sitting on a railing at Harajuku station with Eileen, waiting for some techers in Tokyo to call and tell us their plans. I had been approached by a few people asking for directions in English - even though some looked Japanese. Anyway, this time a Japanese man approached me and asked me, "日本語で喋ますか‚" (Do you speak Japanese?). I replied that I spoke some, and he asked me if I lived in Japan. I replied in the affirmative, and he beckoned one of the women he was with to help him explain. They asked how long I was living in Japan, and I told them until September.

At that point they thanked me and it looked like they were done asking questions. I asked them why they wanted to know, and they explained that the man is a fashion designer and he wants me to be a model for him.

I briefly considered what it'd be like to have such a job that is so antithetical to my nature. It was easy to discard the possibility, though the notion is entertaining.

I haven't posted in a while, mostly because of the physical and mental exhaustion from climbing Mt. Fuji throughout Saturday night, fighting the cold to watch the sunrise, and descending through searing sands of pumice the following afternoon. But I'll get to that shortened story later.

Three weekends ago, I met my family in Narita airport, outside of Tokyo. I found my mom only a couple seconds before she reached to insert some coins into the public telephone to call me. They were still in one piece (well, four), though Sam hadn't slept on the flight. We took the trains to their hotel in Chiba, grabbed some traditional Japanese dinner, and went out to see the fireworks festival at the other end of Chiba. I like the fact that there are so many occasions for fireworks here. In America, there's really only the fourth of July. (I stole most of the photos taken during my family's trip from Craig)

Fireworks in Chiba
That night, though, I discovered that among the main channels available to the Japanese public there was one giving a proof of the Cayley-Hamilton theorem, which is that a square matrix is a zero of its own characteristic polynomial. My point is: would you ever see proofs from intermediate linear algebra on American television? Instead, people are content to just say they're bad at math. No one admits they are bad at reading or writing, because it's embarrassing, but mathematical inability is proudly touted by American high school students. I digress, mainly because I'm sad to see the U.S. loosing its edge in math and science.

The next day we went into Akihabara, where my dad bought a digital video camera. We ate that night at a pretty good sushi place on the top of the enormous electronics department store, Yodabashi Camera.

On Monday they headed off on a bullet train to Kyoto, the old capital of Japan.

Shinkansen
Kinkakuji
bamboo
Somewhere in that interval they found the time to visit a driving range. As an aside, it was during this time that Sam missed the rankings for his high school golf team, but after his return he has already ascended to the top spot, even as a sophomore </bragging>.

gorufu
Samuel
I met them on Friday in Tokyo. That weekend we did all sorts of things that have since turned into a collection of unordered memories. We ate at an Italian restaurant that uses squid ink in its dough, so that it turns completely black. It tasted the same, though. During one particularly hot afternoon, we watched "Ocean's 13" in Ginza and ended up next to a kind of crazy, friendly, 83-year-old man. He spoke English pretty well and drew a sketch of my dad that was amazingly accurate, though it made him look slightly Japanese. He claimed that people said he looked like John Wayne from the nose up, and I could kind of see what he was talking about. He fell asleep for most of the movie.

During one sweltering morning, we visited the Imperial Palace Garden.

The next weekend I went with Andrew and Eileen (two Caltech students) to Odaiba by way of a ferry from Asakusa. On the boat I sat next to a Dutch man in his seventies. He was bone thin, but he looked like he was in his late fifties, and after a bit of conversation, I learned that he had command of at least six languages: Dutch, German, French, Italian, English, and Esperanto. He was in Tokyo with an Esperanto tour group, but he didn't know those in the group very well; there weren't any other Dutch people in the group. He said he loved Italian the most, as it's the most beautiful. Apparently he used to teach French, but since his retirement he likes to travel and learn languages. I can only hope I will still be able to learn at that age.

At Odaiba, we walked around and looked at things. Here are some pictures of those things:

Umi

The Statue of Liberty in Tokyo

Sunset over Tokyo

Yori no fune

Yori no sora

Afterwards we saw Tokyo Tower.

Tokyo Tower

The following weekend we decided to climb Mt. Fuji. Andrew was sick, so Eileen and I took a bus to the fifth station on Mt. Fuji.

The 5th Station

me_at_go_goume

Filed under: Japan

No Comments

9
Jul/070

Leyan and Cathy arrive

On Saturday's misty morning I awoke at 10 am, showered, and asked Mrs. Yamamoto how to get to the right bus stop. We realized I only had 4 minutes to get there, and she couldn't convey exactly how to get there since she knows very little English and the route was complex, so we went running down the street for a little way-she in flip-flops-until I understood exactly where to go.

I boarded the bus for Anegasaki Station and, once there, I took the train to Chiba Station. After some hunting, I found the right place to get my hair cut. I showed the stylist my driver's license and Caltech ID, and that was enough to get what I wanted, aside from the occasional request. The whole operation took about ten minutes, so I grabbed lunch and took the train to Narita Airport to meet Leyan and Cathy as they arrived from China. I soon found out the hard way that "Narita" means the city, and a few stops after that is Narita Airport. So I had to wait an hour for the next train to go a couple stops to the airport. Then I found out the hard way that there are two terminals in Narita Airport and of course I would choose the wrong one first.

Miraculously, Leyan just appeared by my side as I walked through the arrivals area. So he, Cathy, and I hopped on a long series of trains that would take about 3 hours to arrive at Eileen's station.

Leyan
We had a nice dinner consisting mostly of sashimi, but Eileen was sick and accidentally ordered an alcoholic drink that exacerbated her condition.

The next day we took a few trains to Hiratsuka to attend the Tanabata festival there, which is the largest celebration in the Kantou region. Tanabata is a traditional Japanese star festival that celebrates the meeting of Vega and Altair. There were tons of people flowing in from Tokyo, many wearing kimonos.

big pimpin'
Tanabata
All the streets were lined with tables selling food or offering games, and overhead there were very large decorations that were apparently part of a contest. One popular game consisted of trying to catch goldfish with a small, flat, circular paper net. The challenge comes from the fact that the paper breaks easily when wet. There was a tiny turtle version.

Kame no yama!!
Cathy thought the turtles were particularly cute and pointed out this little one riding the big one.

Kame kuruma
There were all sorts of fried meats and wondrous new foods. Here was a chocobanana station.

Bana? Nope. Bananana? Oh, too far.
Here are Cathy and Leyan drinking their fizzy drinks called "Ramune."

This seems like an ad
Leyan got ikayaki (fried squid). It was pretty good.

Ikayaki
I caught the elusive "eww" face.

Cathy's eww face
Leyan transforms.

Ikaleyan
After the Tanabata festival, we went to an onsen (hot springs/spa) in the countryside. Afterward Leyan carried Cathy down the hill. I liked these blurry pictures better than the sharp ones.

Always someone's carrying...Cathy
Carrying Cathy - Ben Folds
I took a few photos of the inada (rice fields).

Inada
At 6:15 pm, I left from the station near Eileen's place and headed for Shinjuku station by train. On the way, I met a university student who looked up the fastest route home for me on his cell phone. With his help, I was able to jump on a rapid express train that allowed me to return to my room at 9:00 pm. All in all an exciting weekend.