Author Archive

You are currently browsing Vishal Lama's articles.

Solution to POW-5: A “hard” integral!

June 27, 2008 in Elementary Math Problem Solving, Problem Corner, Problem of the Week (POW), Puzzles | Tags: hard integral | by Vishal Lama | 10 comments

We got some very good response to our last week’s problem from several of our “regular” problem-solvers as well as several others who are “new”. There were solutions that were more “algebraic” than others, some that had a more “trigonometric” flavor to them and some that had a combination of both. All the solutions we received this time were correct and they all deserve to be published, but for the sake of brevity I will post just one.

Solution to POW-5: (due to Animesh Datta, Univ of New Mexico)

Note that the given integral may be written as

$\displaystyle \int \frac{x^2 - 1}{x(x^2 + 1) \sqrt{x^2 + 1/x^2}} \, dx$

$\displaystyle = \int \frac{1 - 1/x^2}{(x + 1/x) \sqrt{(x + 1/x)^2 - 2}} \, dx$ .

Now, we use the substitution $t = x + 1/x$ , which transforms the integral into

$\displaystyle \int \frac1{t \sqrt{t^2 - 2}} \, dt$ .

Finally, we use one last (trigonometric) substitution $t = \sqrt{2} \sec \theta$ , which transforms the integral into $\displaystyle \int \frac1{\sqrt{2}} \, d\theta$ , which evaluates to $\theta /\sqrt{2} + C$ , which equals $\displaystyle \frac1{\sqrt2} \arctan \sqrt{\frac12 (x^2 + \frac1{x^2})} + C$ . And this is our final answer!

Watch out for the next POW that will be posted by Todd!

Source: I had mentioned earlier that Carl Lira had brought this integral to our attention, and he in turn had found it in the MIT Integration Bee archives. This one was from the year 1994.

Trivia: Four out of the six people who sent correct solutions are either Indians or of Indian origin! Coincidence?

POW-5: A “hard” integral!

June 19, 2008 in Elementary Math Problem Solving, Problem Corner, Problem of the Week (POW) | Tags: hard integral | by Vishal Lama | 4 comments

Time for our next problem in the POW series! Earlier, Todd and I deliberated for a bit on whether we should pose a “hard” Ramanujan identity (involving an integral and Gamma function) as the next POW, but decided against doing it. Perhaps, we may do so some time in the future.

Okay, the following integral was brought to our attention by Carl Lira, and for the time being I won’t reveal the actual source of the problem.

Compute $\displaystyle \int \frac{x^2 - 1}{(x^2 + 1) \sqrt{x^4 + 1}} \, dx$ .

It is “hard” or “easy” depending on how you look at it!

Please send your solutions to topological[dot]musings[At]gmail[dot]com by Wednesday, June 26, 11:59pm (UTC); do not submit solutions in Comments. Everyone with a correct solution gets entered in our Hall of Fame! We look forward to your response.

Firefox 3.0 is now ready!

June 17, 2008 in Uncategorized | Tags: Firefox 3.0 | by Vishal Lama | 1 comment

Don’t forget to download Firefox 3.0 today!

Time for another Republican President… again?

June 3, 2008 in Uncategorized | Tags: democratic party, hillary clinton, US politics | by Vishal Lama | 18 comments

Update: Look for the ’sexism’ video at the end of this post that essentially strengthens my argument about the media treatment meted out to a woman, who was/is as capable as any other candidate, running for a very high office in America, the world’s oldest democracy and whose founding fathers, as we learn from history, were the children of The Enlightenment!

———————————

With the Democratic primary race practically over now and knowing, as we all do, who the nominee is going to be, I just couldn’t resist writing a post on this one, having avoided writing anything about politics all this while.

Well, it was quite appalling to see/hear all these months that when it came to Hillary the discussions/commentaries in the so-called “mainstream” media were similar to ones that are generally heard in men’s locker rooms, while Obama has been treated almost like a God-like figure. And while Hillary’s “racist” remarks were dissected/analyzed with great relish, no one, it seemed to me, paid any particular attention to the disgusting misogynist remarks directed at her throughout the primary campaign season, with the result that the Democratic party has managed, or so it seems, to lose its grip over white women voters now. I have a feeling that this is going to cost the Democrats another general election. (Of course, I could be wrong; I am not a political “pundit”, after all!)

So much has my mother been miffed/angry at the blatant sexist remarks openly made in the media against Hillary that she has vowed now to vote for McCain this Fall. To her, the contest has “demonstrated” yet again that women still haven’t been able to break the glass ceiling in this male-dominated world. Is anyone listening to women voters like her?

A video sample:

In mathematical parlance, this is the only instance in which Left = Right, if you know what I mean.

“Problem of the Week” (POW) Series

May 14, 2008 in Elementary Math Problem Solving, Problem Corner, Problem of the Week (POW) | Tags: math problem solving | by Vishal Lama | 5 comments

Todd and I, after some discussion, have decided to start a new series of posts called “Problem of the Week“. Since the title is self-explanatory, there is nothing much to write about, except that this series will be a permanent fixture on our blog. Each week we will post a problem (unless both of us are too busy), and we invite solutions from all our readers, regular or not; in most cases solutions should be submitted through email within a week after the post. To keep things fair, we ask readers not to submit solutions in the comment section of a post. At the end of the allotted time, we will then select the most elegant solution (or anyway, one that we like) to a given problem, and post it together with the name of the proposer. (Note: solutions may be edited, or composed from solutions of more than one proposer.) Other people who submit correct solutions will also be acknowledged. In addition, credit will be given to all such people by having their names enshrined in the Problem-Solving Hall of Fame page, forever! Who could ask for anything more?!

Most of our problems will be “elementary”, meaning they won’t require knowledge of advanced areas of mathematics; generally they will require some knowledge of subjects such as elementary number theory, college-level calculus, basic algebra, trigonometry, inequalities, etc., and some “mathematical maturity”.

Please submit solutions to topological[dot]musings[At]gmail.com (remove the characters within the square brackets and replace them with the appropriate ones). You may send in your solutions in pdf, LaTeX or text format. (Though we prefer LaTeX and/or pdf submissions, we ask you not to worry too much about the format.) [Added May 15: in case of multi-part problems, please submit all the parts you intend to solve in one mailing. Credit will be awarded for each part correctly solved.]

I guess that’s it! Keep checking the blog for the next POW problem!

POW-1: An “elementary” divisibility problem

May 12, 2008 in Elementary Math Problem Solving, Problem Corner, Problem of the Week (POW) | Tags: divisibility problem | by Vishal Lama | 7 comments

[Update: I have decided to pose at least one problem (or perhaps, two problems) a week from now and invite solutions to those problems from the readers. This should be exciting. I am sure all of you would want your names to be listed in the Problem-Solving Hall of Fame page! ]

This post is about getting the readers of this blog to participate! And so, let me pose an elementary divisibility problem and invite solutions from the readers. “Elementary” doesn’t necessarily mean “easy”, by the way. It just means elementary methods can be used to solve the problem. I am particularly looking for elegant solutions, though all kinds of solutions are welcome. Readers with correct solutions will be given credit and their names will be included in the Problem-Solving Hall of Fame page on this blog! So, go ahead, write down your solutions.

Problem: Suppose $x$ and $y$ are two positive natural numbers such that $x^2 + xy + 1$ is divisible by $y^2 + xy + 1$ . Prove that $x = y$ .

Stolz-Cesàro Theorem

May 8, 2008 in Elementary Math Problem Solving, Problem Corner, Some theorems | Tags: cesaro, limit, stolz | by Vishal Lama | 10 comments

The following theorem, I feel, is not very well-known, though it is a particularly useful one for solving certain types of “limit” problems. Let me pose a couple of elementary problems and offer their solutions. First, the theorem.

Stolz-Cesàro: Let $(a_n)_{n \ge 1}$ and $(b_n)_{n \ge 1}$ be two sequences of real numbers, such that $(b_n)$ is positive, strictly increasing and unbounded. Then,

$\displaystyle \lim_{n \to \infty} \frac{a_n}{b_n} = \lim_{n \to \infty} \frac{a_{n+1} - a_n}{b_{n+1} - b_n}$ ,

if the limit on the right hand side exists.

The proof involves the usual $\epsilon - \delta$ method, and I will avoid presenting it here since it isn’t particularly interesting. Just as Abel’s lemma is the discrete analogue of integration by parts, the Stolz-Cesàro theorem may be considered the discrete analogue of L’Hospital’s rule in calculus.

Problem 1: Evaluate the limit $\displaystyle \lim_{n \to \infty} \frac{1^k + 2^k + \ldots + n^k}{n^{k+1}}$ , where $k \in \mathbb{N}$ .

Solution: One may certainly consider the above limit as a Riemann-sum which may then be transformed into the integral $\displaystyle \int_0^1 x^k \, dx$ , which then obviously evaluates to $1/(k+1)$ . But, we will take a different route here.

First, let $a_n = 1^k + 2^k + \ldots + n^k$ and $b_n = n^{k+1}$ . Then, we note that the sequence $(b_n)$ is positive, strictly increasing and unbounded. Now,

$\displaystyle \lim_{n \to \infty} \frac{a_{n+1} - a_n}{b_{n+1} - b_n} = \lim_{n \to \infty} \frac{(n+1)^k}{(n+1)^{k+1} - n^{k+1}}$

$\displaystyle = \lim_{n \to \infty} \frac{(n+1)^k}{\left(1 + \binom{k+1}{1}n + \binom{k+1}{2}n^2 + \ldots + \binom{k+1}{k}n^k + n^{k+1}\right) - n^{k+1}}$

(using the binomial theorem)

$\displaystyle = \lim_{n \to \infty} \frac{(n+1)^k / n^k}{\left(1 + \binom{k+1}{1}n + \binom{k+1}{2}n^2 + \ldots + \binom{k+1}{k}n^k \right) / n^k}$

$\displaystyle = \lim_{n \to \infty} \frac{(1 + 1/n)^k}{\binom{k+1}{k}} = \frac1{k+1}$ .

Therefore, using the Stolz-Cesàro theorem, we conclude that the required limit is also $1/(k+1)$ .

Let us now look at another problem where applying the aforesaid theorem makes our job a lot easier. This problem is an example of one that is not amenable to the other usual methods of evaluating limits.

Problem 2: Let $k\geq 2$ be integers and suppose $C: y = \sqrt {2x + 1}\ (x > 0)$ . Given the tangent line at the point $(a_{k},\, \sqrt {2a_{k} + 1})$ from the point $(0, k)$ to $C$ , evaluate

$\displaystyle \lim_{n\to\infty}\frac {1}{n^{3}}\sum_{k = 2}^{n}a_{k}$ .

Solution:(This is basically the solution I had offered elsewhere a while ago; so, it’s pretty much copy/paste!)

$\displaystyle y = \sqrt {2x + 1}\Rightarrow \frac {dy}{dx} = \frac {1}{\sqrt {2x + 1}}$ .

So, the equation of the tangent line at the point $(a_{k}, \sqrt {2a_{k} + 1})$ is given by

$\displaystyle y - \sqrt {2a_{k} + 1} = \frac {1}{\sqrt {2a_{k} + 1}}(x - a_{k}).$

Since the point $(0,k)$ lies on this line, we must have

$\displaystyle k - \sqrt {2a_{k} + 1} = \frac {1}{\sqrt {2a_{k} + 1}}( - a_{k})$

The above, after squaring and some algebraic manipulation yields
$a_{k}^{2} + 2(1 - k^{2})a_{k} + 1 - k^{2} = 0$ , which implies $a_{k} = (k^{2} - 1) + k(\sqrt {k^{2} - 1})$ . We drop the negative root because $a_{k} > 0$ for all $k\ge 2$ .

(This is where the Stolz-Cesàro theorem actually comes into play!)

Now, let $(b_{n})$ and $(c_{n})$ be two sequences such that $\displaystyle b_{n} = \sum_{k = 2}^{n}a_{k}$ and $c_{n} = n^{3}.$
Note that $(c_{n})$ is a positive, increasing and unbounded sequence.

Therefore, $\displaystyle \lim_{n\to \infty}\frac {b_{n + 1} - b_{n}}{c_{n + 1} - c_{n}} = \lim_{n\rightarrow \infty}\frac {\sum_{k = 2}^{n + 1}a_{k} - \sum_{k = 2}^{n}a_{k}}{(n + 1)^{3} - n^{3}} = \lim_{n\rightarrow \infty}\frac {a_{n + 1}}{3n^{2} + 3n + 1}$

$\displaystyle = \lim_{n\to \infty}\frac {(n + 1)^{2} - 1 + (n + 1)\sqrt {(n + 1)^{2} - 1}}{3n^{2} + 3n + 1}$

$\displaystyle = \lim_{n \to \infty} \frac{(1 + 1/n)^2 - 1/n^2 + (1 + 1/n)\sqrt{1 + 2/n}}{3 + 3/n + 1/n^2}$

$= 2/3$ .

Therefore, by the Stolz- Cesàro theorem, we have

$\displaystyle \lim_{n\to \infty}\frac {b_{n}}{c_{n}} = 2/3 \,$ , and so

$\displaystyle \lim_{n\to \infty}\frac {1}{n^{3}}\sum_{k = 2}^{n}a_{k} = 2/3$ .

I. The Category of Sets

April 27, 2008 in Category Theory, Category Theory for Beginners, Exposition, Math Topics | Tags: beginner, Category Theory, sets | by Vishal Lama | 2 comments

I will write a series of posts as a way of gently introducing category theory to the ‘beginner’, though I will assume that the beginner will have some level of mathematical maturity. This series will be based on the the book, Conceptual Mathematics: A first introduction to categories by Lawvere and Schanuel. So, this won’t go into most of the deeper stuff that’s covered in, say, Categories for the Working Mathematician by Mac Lane. We shall deal only with sets (as our objects) and functions (as our morphisms). This means we deal only with the Category of Sets! Therefore, the reader is not expected to know about advanced stuff like groups and/or group homomorphisms, vector spaces and/or linear transformations, etc. Also, no knowledge of college level calculus is required. Only knowledge of sets and functions, some familiarity in dealing with mathematical symbols and some knowledge of elementary combinatorics are required. That’s all!

Sets, maps and composition

An object (in this category) is a finite set or collection.

A map $f: A \to B$ (in this category) consists of the following:

i) a set $A$ called the domain of the map;

ii) a set $B$ called the codomain of the map; and

iii) a rule assigning to each $a \in A$ , an element $b \in B$ .

We also use ‘function’, ‘transformation’, ‘operator’, ‘arrow’ and ‘morphism’ for ‘map’ depending on the context, as we shall see later.

An endomap $f: A \to A$ is a map that has the same object as domain and codomain, which in this case is $A$ .

An endomap in which $f(a) = a$ for every $a \in A$ is called an identity map, also denoted by $1_A$ .

Composition of maps is a process by which two maps are combined to yield a third map. Composition of maps is really at the heart of category theory, and this will be evident in plenty in the later posts. So, if we have two maps $f: X \to Y$ and $g:Y \to Z$ , then $g \circ f: X \to Z$ is the third map obtained by composing $f$ and $g$ . Note that $g \circ f$ is read ‘ $g$ following $f$ ‘.

Guess what? Those are all the ingredients we need to define our category of sets! Though we shall deal only with sets and functions, the following definition of a category of sets is actually pretty much the same as the general definition of a category.

Definition: A CATEGORY consists of the following:

(1) OBJECTS: these are usually denoted by $A, B, C, \ldots$ etc.

(2) MAPS: these are usually denoted by $f, g, h, \ldots$ etc.

(3) For each map $f$ , one object as DOMAIN of $f$ and one object as CODOMAIN of $f$ . So, $f: A \to B$ has domain $A$ and codomain $B$ . This is also read as ‘ $f$ is a map from $A$ to $B$ ‘.

(4) For each object $A$ , there exists an IDENTITY MAP, $1_A$ . This is also written as $1_A: A \to A$ .

(5) For each pair of maps $f: A \to B$ and $g: B \to C$ , there exists a COMPOSITE map, $g \circ f: A \to C$ . ( ‘ $g$ following $f$ ‘.)

such that the following RULES are satisfied:

(i) (IDENTITY LAWS): If $f: A \to B$ , then we have $1_B \circ f = f$ and $f \circ 1_A = f$ .

(ii) (ASSOCIATIVE LAW): If $f: A \to B , \, g: B \to C$ and $h: C \to D$ , then we have $(h \circ g)\circ f = h \circ (g \circ f)$ . ( ‘ $h$ following $g$ following $f$ ‘) Note that in this case we are allowed to write $h \circ g \circ f$ without any ambiguity.

Exercises: Suppose $A = \{ a, b, c, d \}$ and $B = \{ 1, 2, 3 \}$ .

(1) How many maps $f$ are there from $A$ to $B$ ?

(2) How many maps $f$ are there from $A$ to $A$ ?

(3) How many maps $f$ are there from $B$ to $A$ ?

(4) How many maps $f$ are there from $B$ to $B$ ?

(5) How many maps $f$ are there from $A$ to $A$ satisfying $f \circ f = f$ ?

(This is a non-trivial exercise for the general case in which $|A| = n$ for some positive integer $n$ .)

(6) How many maps $g$ are there from $B$ to $B$ satisfying $g \circ g = g$ ?

(7) Can you find a pair of maps $f: A \to B$ and $g: B \to A$ such that $g \circ f = 1_A$ . If yes, how many pairs can you find?

(8 ) Can you find a pair of maps $h: B \to A$ and $k: A \to B$ such that $k \circ h = 1_B$ . If yes, how many pairs can you find?

Bonus exercise:

How many maps $f: A \to B$ are there if $A$ is the empty set and $|B| = n$ for some $n \in \mathbb{N}$ ? What if $|A| = n$ and $B$ is the empty set? What if both $A$ and $B$ are empty?

Milk and Tea puzzle

April 14, 2008 in Uncategorized | Tags: math puzzle | by Vishal Lama | 3 comments

[Update: Look for another (slicker) solution I found after coming up with the first one.]

My friend, John, asked me today if I had a solution to the following (well-known) problem which may be found, among other sources, in Chapter Zero (!) of the very famous book, Mathematical Circles (Russian Experience).

Three tablespoons of milk from a glass of milk are poured into a glass of tea, and the liquid is thoroughly mixed. Then three tablespoons of this mixture are poured back into the glass of milk. Which is greater now: the percentage of milk in the tea or the percentage of tea in the milk?

Note that there is nothing special about transferring three tablespoons of milk and/or tea from one glass to another - the problem doesn’t really change if we transfer one tablespoon of milk/tea instead, and that there is nothing special about transferring “volumes” - we could instead keep a count of, say, the number of molecules transferred. We may, therefore, pose ourselves the following analogous “discrete” problem whose solution provides more “insight” into what’s really going on.

Jar W contains $n$ white objects (and no other objects) and jar B contains $n$ black objects (and no other objects.) We transfer $k$ objects from jar W to jar B. We then thoroughly mix - in fact, we don’t have to - the contents of jar B, following which we transfer $k$ objects, this time, from jar B to jar W. Which is greater now: the percentage of black objects in jar W or the percentage of white objects in jar B?

Solution 1: Let us keep track of the number of black and white objects in both the jars before and after the transfers of $k$ objects from one jar to another. So, initially, in jar W,

# of white objects = $n$ , and # of black objects = $0 \,$ .

Also, in jar B,

# of white objects = $0 \,$ , and # of black objects = $n$ .

Now, we transfer $k$ objects from jar W to jar B. So, in jar W,

# of white objects = $n-k$ , and # of black objects = $0 \,$ .

Also, in jar B,

# of white objects = $k$ , and # of black objects = $n$ .

Finally, we transfer $k$ objects from jar B to jar W. Let the number of white objects out of those $k$ objects be $k_1$ . Then, the number of black objects transferred equals $k-k_1$ . Therefore, now, in jar W,

# of white objects = $n-k + k_1$ , and # of black objects = $k-k_1$ .

Also, in jar B,

# of white objects = $k-k_1$ , and # of black objects = $n - (k-k_1)$ .

From here, it is easy to see that the percentage of black objects in jar W is the same as the percentage of white objects in jar B! And, we are done.

Solution 2: (I think this is a slicker one, and I found it after pondering a little over the first solution I wrote above!) This one uses the idea of invariants, and there are, in fact, two of ‘em in this problem! Note that at any given time,

# of white objects = # of black objects = $n$ .

The above is the first invariant.

Also, note that after we transfer $k$ objects from jar W to jar B and then $k$ objects from jar B to jar W, the number of objects in each jar is also $n$ . This is the second invariant. And, now the problem is almost solved!

Suppose, after we do the transfers of $k$ objects from jar W to jar B and then from jar B to jar W, the # of white objects in jar W is $k$ . Then it is easy to see that the # of black objects in jar W is $n-k$ (using the second invariant mentioned above.) Similarly, using the first invariant, the # of white objects in jar B = $n-k$ . Therefore, using the second invariant again, the # of black objects in jar B = $n - (n-k) = k$ . And, from this the conclusion immediately follows!

Three friends, camping and logs of wood!

April 13, 2008 in Puzzles | Tags: campfire, math puzzle, Yakov Perelman | by Vishal Lama | 23 comments

I wasn’t keeping well - nothing too serious though - over the past few days, and going through a slight bout of depression doesn’t help very much either. I think I have recovered now. During such periods, it helps (I think) to keep the mind busy over some light puzzle(s) just so it remains active and healthy. Anyway, let me pose a nice puzzle that I first read in a book by Yakov I. Perelman many years ago, and I invite you to post your solutions. In keeping with the spirit of the puzzle, I will stick to Russian names and currency, even though the names I use below aren’t the same as the ones used in the original puzzle.

Anna, Bogdana and Calina are three young mathematicians who decide, one fine day, to go camping. During camping, in the evening they light a campfire to keep themselves warm and also to discuss (what else?) mathematics! Anna and Bogdana had brought with them three and five logs of wood, respectively, but unfortunately, Calina forgot to bring any log of wood with her. Instead, she gave 8 rubles to the other two girls. If Calina didn’t want any money back and if all the eight logs of wood were used for building the campfire, how should Anna and Bogdana distribute the 8 rubles between themselves in a fair manner?

Petition to support maths, statistics, and computing at the University of Southern Queensland (USQ)

April 6, 2008 in Uncategorized by Vishal Lama | No comments

Please visit this page on Prof. Tao’s blog to support an important online petition. You may want to read more about the context/background over here.

Firefox 3 beta 4

March 26, 2008 in Uncategorized | Tags: Firefox 3, Beta 4 | by Vishal Lama | 1 comment

[Update: Firefox 3 Beta 5 is out - the last beta version! And it is supposedly the fastest browser out there. So, far it's been using memory not more than ~~150~~ 200 Mb!]

I have been wanting to respond to some of the comments I’ve received over the past week but haven’t had enough time to do so. I will certainly respond some time soon.

For now, I just wish to point out to folks who use Firefox 2 that Firefox 3 Beta 4 has been released. Well, it is only meant for developers and testers for now, but having installed and used it over the past several days, I can say it’s a much better version of the Firefox browser. The biggest problem (I’ve had) with the current version of Firefox is it uses an enormous amount of memory mostly due to memory leaks. Keep it running for several days - I hardly log off - and the browser takes up as much as 700-800Mb of memory, sometimes even consuming a gigabyte, which is plain insane! Due to this, I had seriolusly considered switching to Flock or IE altogether. But, now I am very satisfied with the new beta version. It mostly uses around 150Mb of memory while never exceeding ~~200Mb~~ 250Mb, which really shows that the Firefox team has had been working hard on the new version.

Go ahead and download/install the new beta version and test it yourself. I haven’t had any problems thus far. The only downside of using the beta version is your add-ons will not work, but that is hardly an issue, at least to me, for now.

Inclusion-Exclusion Principle: Counting all the objects outside the oval regions!

March 20, 2008 in Exposition, Some theorems | Tags: Polya, Szego, inclusion-exclusion principle | by Vishal Lama | 14 comments

Part 2:

After having understood the inclusion-exclusion principle by working out a few cases and examples in my earlier post, we are now ready to prove the general version of the principle.

As with many things in mathematics, there is a “normal” way of doing proofs and there is the “Polya/Szego” way of doing proofs. (Ok, ok, I admit it’s just a bias I have.) I will stick to the latter. Ok, let’s state the principle first and follow it up with its proof in a step-by-step fashion.

Inclusion-Exclusion Principle: Let there be a set of $N$ objects. Suppose out of these $N$ objects, there are $N_a$ objects of type $a$ , $N_b$ objects of type $b, \ldots ,$ $N_k$ objects of type $k$ and $N_l$ objects of type $l$ . Also, suppose $N_{ab}, N_{ac}, \ldots , N_{abc}, \ldots , N_{ab \ldots kl}$ denote the number of objects that are simultaneously of type $a$ AND $b,$ $a$ AND $c, \ldots , a, b$ AND $c, \ldots , a, b, c, k$ AND $l,$ respectively. Then, the number of objects that are NOT of type $a, b, c, \ldots , k, l$ is

$N - (N_a + N_b + \ldots + N_k + N_l)$

$+ (N_{ab} + N_{ac} + \ldots + N_{kl})$

$- (N_{abc} + \ldots ) + \ldots$

$\pm N_{abc \ldots kl}$ .

— Notation —

Let $U$ (finite or infinite) be the universe of discourse. Suppose $A \subset U$ . Then, the characteristic function $1_A: U \to \{ 0, 1 \}$ of $A$ is defined as

$1_A (x) = 1$ if $x \in A$ ,

and $1_A(x) = 0$ otherwise, for all $x \in U$ .

For example, suppose $U = \{ 1, 2, 3, 4, \ldots , 29, 30 \}$ . Let $A = \{ 2, 4, 6, \ldots , 28, 30 \}$ (i.e. even integers.) Then, $1_A(2) = 1_A(26) = 1, 1_A(3) = 1_A(29) = 0$ , and so on.

Note: $1_U (x) = 1$ and $1_{\emptyset}(x) = 0$ for all $x \in U$ . Here, $\emptyset$ denotes the empty set. Due to this, we will use $1$ and $1_U$ interchangeably from now.

—

Lemma 1: $A \subset B$ iff $1_A(x) \le 1_B(x)$ for all $x \in U$ .

Proof: We first prove the “only if”part. So, suppose $A \subset B$ . Let $x \in U$ . If $x \in A$ , then $1_A(x) = 1$ . But, we also have $x \in B$ , in which case, $1_B(x) = 1$ . If, on the other hand, $x \notin A$ , then $1_A(x) = 0 \le 1_B(x)$ . Hence, in either case, $1_A(x) \le 1_B(x)$ for all $x \in U$ .

We now prove the “if” part. So, suppose $1_A(x) \le 1_B(x)$ for all $x \in U$ . Let $x \in A$ . Then, $1_A(x) = 1$ , which forces $1_B(x) = 1$ , which implies $x \in B$ . Hence, $A \subset B$ , and this completes our proof.

Note: If $U$ is finite, then $\displaystyle |A| = \sum_{x \in U}1_A(x)$ .

Lemma 2: $1_{A^c}(x) = 1 - 1_A(x) ,$

$1_{A \cap B}(x) = 1_A(x) 1_B(x),$ and

$1_{A \cup B}(x) = 1 - (1 - 1_A(x))(1 - 1_B(x))$

for all $x \in U$ . (Here, $A^c$ is the complement of $A$ .)

Proof: The proof for each case is elementary.

Lemma 3: Suppose $U$ is finite. If $A, B, C, \ldots \subset U$ , then the characteristic function of $A \cup B \cup C \cup \ldots$ is $1 - (1 - 1_A)(1 - 1_B)(1 - 1_C) \ldots$ , i.e.

$1_{A \cup B \cup C \cup \ldots}(x) = 1 - (1 - 1_A(x))(1 - 1_B(x))(1 - 1_C(x)) \ldots$ for all $x \in U$ .

Proof: Note the above is an extension of the third part of lemma $(2)$ . A simple induction on the number of subsets of $U$ proves the result.

— Proof of the inclusion-exclusion principle —

Now, suppose $A, B, C, \ldots, K, L$ are subsets of objects of type $a, b, c, \ldots, k, l$ , respectively. Observe that the set of objects that are NOT of type $a, b, c, \ldots , k, l$ is simply the region outside of all the oval regions! (Look at the previous post to see what this means.) And this region is simply the subset $(A \cup B \cup B \cup \ldots \cup K \cup L)^c$ . Using the first part of lemma $(2)$ , we see that the characteristic function of this outside region is $1 - 1_{A \cup B \cup B \cup \ldots \cup K \cup L}$ , which from lemma $(3)$ is the same as

$(1-1_A)(1-1_B)(1-1_C) \ldots (1-1_K)(1-1_L)$ .

Expand the last expression to get

$1 - (1_A + 1_B + 1_C + \ldots)$

$+ (1_A1_B + 1_A1_C + \ldots)$

$- (1_A1_B1_C + \ldots) + \ldots$

$\pm 1_A1_B\ldots 1_L$ .

Now, sum over all the elements of $U$ and use the second part of lemma $(2)$ to obtain the desired result. And this completes our proof.

Inclusion-Exclusion Principle: Counting all the objects outside the oval regions!

March 18, 2008 in Exposition, Some theorems | Tags: inclusion-exclusion principle, venn diagram | by Vishal Lama | No comments

Part 1:

A couple of weeks ago, my friend John (from UK) asked me if I could explain the Inclusion-Exclusion Principle to him. Wikipedia contains an article on the same topic but John felt that it wasn’t a very helpful introduction. So, as promised, here is the post on that topic, though I managed to finish it only after some delay. (Sorry, John!)

As the title of this post suggests, the inclusion-exclusion principle can simply be described as counting all the objects outside the oval regions! We will use Venn diagrams to explain what that means.

Note: $\lfloor x \rfloor$ denotes the greatest integer less than $x$ .

Ok, let’s now “build” the principle step by step.

1. Suppose there are $N$ objects out of which there are exactly $N_a$ objects of type $a$ . How many objects are NOT of type $a$ ? The answer is obvious: $N - N_a$ . The Venn diagram below depicts the answer pictorially. The rounded rectangular region (with the orange border) is the set of all $N$ objects, and the oval region (with the blue border) is the set of all $N_a$ objects of type $a$ . Then, the remaining white region that is outside the oval region denotes the set of all objects that are NOT of type $a$ , and clearly, there are $N - N_a$ of ‘em.

Indeed, let us take a simple example. Consider the set of first thirty natural numbers: $\{ 1, 2, \ldots , 30 \}$ . So, $N = 30$ . Now, out of these thirty integers, let $N_2$ be the number of integers divisible by $2$ . Then, $N_2 = \lfloor 30/2 \rfloor = 15$ . It is easy to see that the number of integers NOT divisible by $2$ equals $N - N_2 = 30 - 15 = 15$ , which is what we would expect if we were to list all the integers not divisible by $2$ . Indeed, those integers are $1, 3, 5, \ldots , 29$ .

2. Now, suppose there are $N$ objects out of which there are exactly $N_a$ objects of type $a$ and $N_b$ objects of type $b$ . Also, suppose there are exactly $N_{ab}$ objects that are of both type $a$ AND $b$ . Then, how many objects are NOT of type $a$ OR $b$ ? The Venn diagram below illustrates this case.

Again, we are counting the number of objects outside the two oval regions. To answer the above question, we first need to determine the number of objects inside the two oval regions, and then subtract this number from the total, which is $N$ . Now, one might be tempted to think that the number of objects inside the two oval regions is simply $N_a + N_b$ . But this is only true if the two oval regions don’t intersect (i.e. they have no objects in common.) In the general case, however, the expression $N_a + N_b$ counts $N_{ab}$ twice! And so, we must subtract $N_{ab}$ from the expression to get $N_a + N_b - N_{ab}$ as the exact number of objects inside the two oval regions. We can now see that the number of objects outside the two oval regions equals $N - (N_a + N_b - N_{ab}) = N - (N_a + N_b) + N_{ab}$ , and we are done.

Continuing with our example used earlier, let $N_3$ be the number of integers divisible by $3$ . Also, let $N_6$ be the number of integers divisible by $2$ AND $3$ (i.e. we count multiples of $6$ .) Now, note that $N_3 = \lfloor 30/3 \rfloor = 10$ , and $N_6 = \lfloor 30/6 \rfloor = 5$ .

Thus, using the formula derived above, the number of integers that are NOT divisible by $2$ OR $3$ equals $N - (N_2 + N_3) + N_6 = 30 - (15 + 10) + 5 = 10$ . In fact, we can list these ten integers: $1, 5, 7, 11, 13, 17, 19, 23, 25$ and $29$ ; and this confirms our answer.

3. Now, suppose there are $N$ objects out of which there are exactly $N_a$ objects of type $a$ , $N_b$ objects of type $b$ and $N_c$ objects of type $c$ . Also, let $N_{ab}$ denote the number of objects of type $a$ AND $b$ , $N_{bc}$ the number of objects of type $b$ AND $c$ , $N_{ca}$ the number of objects of type $c$ AND $a$ , and $N_{abc}$ the number of objects of type $a, b$ AND $c$ . Then, how many objects are NOT of type $a, b$ OR $c$ ? This case is illustrated by the Venn diagram shown below.

Once again, let us ask, what is the number of objects inside the three oval regions. A possible answer is $N_a + N_b + N_c$ . Now this will only be true if the three oval regions are pairwise disjoint. In the general case, however, we will have to take care of overcounting, just as we did in $(2)$ earlier. A brief thought will reveal that in the above expression, we have counted each of $N_{ab}, N_{bc}$ and $N_{ca}$ twice and $N_{abc}$ thrice! To take care of this overcounting, we subtract each of $N_{ab}, N_{bc}$ and $N_{ca}$ once from the expression, but in doing so, we also end up subtracting $N_{abc}$ thrice! We thus need to add $N_{abc}$ back into the expression to get $N_a + N_b + N_c - N_{ab} - N_{bc} - N_{ca} + N_{abc}$ , and this expression yields the exact number of objects inside the three oval regions. Therefore, the number of objects outside the three oval regions equals $N - (N_a + N_b + N_c) + (N_{ab} + N_{bc} + N_{ca}) - N_{abc}$ . And, we are done.

Again, continuing with our earlier example, let $N_5$ denote the number of integers divisible by $5$ . Then, $N_5 = \lfloor 30/5 \rfloor = 6$ . Also, let $N_{15}$ denote the number of integers divisible by $3$ AND $5$ (i.e. we are counting multiples of $15$ ); then, $N_{15} = \lfloor 30/15 \rfloor = 2$ . Again, let $N_{10}$ denote the number of integers divisible by $2$ and $5$ ; then $N_{10} = \lfloor 30/10 \rfloor = 3$ . And, finally, let $N_{30}$ denote the number of integers divisible by $2, 3$ and $5$ ; then $N_{30} = \lfloor 30/30 \rfloor = 1$ .

So, the number of integers NOT divisible by $2, 3$ OR $5$ equals $N - (N_2 + N_3 + N_5) + (N_{6} + N_{15} + N_{10}) - N_{30}$

$= 30 - (15 + 10 + 6) + (5 + 2 + 3) - 1 = 8$ . Indeed, those eight integers are $1, 7, 11, 13, 17, 19, 23$ and $29$ .

It isn’t very hard to deduce the formula for the general case when we have a set of $N$ objects, out of which there are $N_a$ objects of type $a$ , $N_b$ objects of type $b$ , and so on. The proof of the general formula will follow in the next post, which may include a couple of problems/solutions involving this principle.

2008 CURM Conference & MAA Intermountain Section Meeting

March 16, 2008 in Math Conferences | Tags: BYU, CURM conference, math | by Vishal Lama | 2 comments

I attended the CURM Conference & MAA Intermountain Section Meeting yesterday at BYU, Provo, and had the chance to attend quite a few presentations that I found interesting. There were four presentations in particular that were of special interest to me, and though, right now, I don’t have enough material to blog on ‘em, I think I will eventually find the required material to post some stuff here.

These four presentations were titled

1. Exploration of G-graphs of Non-Abelian Groups: Andrea L. DeWitt & Alys M. Rodriguez (Lamar University)

2. Re-invent the Wheel: can it be done?: Christa Bauer & Jillian Hamilton (Lamar University)

3. Proving Integer Sequence Identities with Paths on Graphs: Megan Craven (St. Peters College)

4. Restricted Rado Numbers: Katrina Luckenbach & Matthew Vieira (St. Peters College)

My All Time Favorite Guitarists (1)

March 10, 2008 in Music | Tags: guitar, joe satriani, Music | by Vishal Lama | No comments

I simply love the sound of the guitar (of all types), and as any amateur guitar player, I have some guitar heroes myself - this has got nothing to do with the popular game Guitar Hero, which I think sucks!

Let me begin by posting several videos of Joe Satriani or “Satch” (as he is popularly known) playing Love Thing, Always with Me Always with You and Starry Night. By the way, Kirk Hammett (Metallica) and Steve Vai were both students of Satch, if you didn’t know.

Enjoy!

Love Thing

Always with Me Always with You

Starry Night

A Method of E. Landau (in complex analysis)

March 10, 2008 in Some theorems | Tags: Polya, Szego, e. landau, maximum modulus principle | by Vishal Lama | 4 comments

[Update: Thanks to Andreas for pointing out that I may have been a little sloppy in stating the maximum modulus principle! The version below is an updated and correct one. Also, Andreas pointed out an excellent post on "amplification, arbitrage and the tensor power trick" (by Terry Tao) in which the "tricks" discussed are indeed very useful and far more powerful generalizations of the "method" of E. Landau discussed in this post. The Landau method mentioned here, it seems, is just one of the many examples of the "tensor power trick".]

The maximum modulus principle states that if $f: U \to \mathbb{C}$ (where $U \subset \mathbb{C}$ ) is a holomorphic function, then $|f|$ attains its maximal value on any compact $K \subset U$ on the boundary $\partial K$ of $K$ . (If $|f|$ attains its maximal value anywhere in the interior of $K$ , then