You are currently browsing Vishal Lama's articles.
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
.
Now, we use the substitution , which transforms the integral into
.
Finally, we use one last (trigonometric) substitution , which transforms the integral into
, which evaluates to
, which equals
. 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? ![]()
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 .
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.
Don’t forget to download Firefox 3.0 today!
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.
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!
[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 and
are two positive natural numbers such that
is divisible by
. Prove that
.
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 and
be two sequences of real numbers, such that
is positive, strictly increasing and unbounded. Then,
,
if the limit on the right hand side exists.
The proof involves the usual 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 , where
.
Solution: One may certainly consider the above limit as a Riemann-sum which may then be transformed into the integral , which then obviously evaluates to
. But, we will take a different route here.
First, let and
. Then, we note that the sequence
is positive, strictly increasing and unbounded. Now,
(using the binomial theorem)
.
Therefore, using the Stolz-Cesàro theorem, we conclude that the required limit is also .
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 be integers and suppose
. Given the tangent line at the point
from the point
to
, evaluate
.
Solution:(This is basically the solution I had offered elsewhere a while ago; so, it’s pretty much copy/paste!)
.
So, the equation of the tangent line at the point is given by
Since the point lies on this line, we must have
The above, after squaring and some algebraic manipulation yields
, which implies
. We drop the negative root because
for all
.
(This is where the Stolz-Cesàro theorem actually comes into play!)
Now, let and
be two sequences such that
and
Note that is a positive, increasing and unbounded sequence.
Therefore,
.
Therefore, by the Stolz- Cesàro theorem, we have
, and so
.
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 (in this category) consists of the following:
i) a set called the domain of the map;
ii) a set called the codomain of the map; and
iii) a rule assigning to each , an element
.
We also use ‘function’, ‘transformation’, ‘operator’, ‘arrow’ and ‘morphism’ for ‘map’ depending on the context, as we shall see later.
An endomap is a map that has the same object as domain and codomain, which in this case is
.
An endomap in which for every
is called an identity map, also denoted by
.
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 and
, then
is the third map obtained by composing
and
. Note that
is read ‘
following
‘.
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 etc.
(2) MAPS: these are usually denoted by etc.
(3) For each map , one object as DOMAIN of
and one object as CODOMAIN of
. So,
has domain
and codomain
. This is also read as ‘
is a map from
to
‘.
(4) For each object , there exists an IDENTITY MAP,
. This is also written as
.
(5) For each pair of maps and
, there exists a COMPOSITE map,
. ( ‘
following
‘.)
such that the following RULES are satisfied:
(i) (IDENTITY LAWS): If , then we have
and
.


(ii) (ASSOCIATIVE LAW): If and
, then we have
. ( ‘
following
following
‘) Note that in this case we are allowed to write
without any ambiguity.

Exercises: Suppose and
.
(1) How many maps are there from
to
?
(2) How many maps are there from
to
?
(3) How many maps are there from
to
?
(4) How many maps are there from
to
?
(5) How many maps are there from
to
satisfying
?
(This is a non-trivial exercise for the general case in which for some positive integer
.)
(6) How many maps are there from
to
satisfying
?
(7) Can you find a pair of maps and
such that
. If yes, how many pairs can you find?
(8 ) Can you find a pair of maps and
such that
. If yes, how many pairs can you find?
Bonus exercise:
How many maps are there if
is the empty set and
for some
? What if
and
is the empty set? What if both
and
are empty?
[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 white objects (and no other objects) and jar B contains
black objects (and no other objects.) We transfer
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
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 objects from one jar to another. So, initially, in jar W,
# of white objects = , and # of black objects =
.
Also, in jar B,
# of white objects = , and # of black objects =
.
Now, we transfer objects from jar W to jar B. So, in jar W,
# of white objects = , and # of black objects =
.
Also, in jar B,
# of white objects = , and # of black objects =
.
Finally, we transfer objects from jar B to jar W. Let the number of white objects out of those
objects be
. Then, the number of black objects transferred equals
. Therefore, now, in jar W,
# of white objects = , and # of black objects =
.
Also, in jar B,
# of white objects = , and # of black objects =
.
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 = .
The above is the first invariant.
Also, note that after we transfer objects from jar W to jar B and then
objects from jar B to jar W, the number of objects in each jar is also
. This is the second invariant. And, now the problem is almost solved!
Suppose, after we do the transfers of objects from jar W to jar B and then from jar B to jar W, the # of white objects in jar W is
. Then it is easy to see that the # of black objects in jar W is
(using the second invariant mentioned above.) Similarly, using the first invariant, the # of white objects in jar B =
. Therefore, using the second invariant again, the # of black objects in jar B =
. And, from this the conclusion immediately follows!
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?
[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.
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 objects. Suppose out of these
objects, there are
objects of type
,
objects of type
objects of type
and
objects of type
. Also, suppose
denote the number of objects that are simultaneously of type
AND
AND
AND
AND
respectively. Then, the number of objects that are NOT of type
is
.
— Notation —
Let (finite or infinite) be the universe of discourse. Suppose
. Then, the characteristic function
of
is defined as
if
,
and otherwise, for all
.
For example, suppose . Let
(i.e. even integers.) Then,
, and so on.
Note: and
for all
. Here,
denotes the empty set. Due to this, we will use
and
interchangeably from now.
—
Lemma 1: iff
for all
.
Proof: We first prove the “only if”part. So, suppose . Let
. If
, then
. But, we also have
, in which case,
. If, on the other hand,
, then
. Hence, in either case,
for all
.
We now prove the “if” part. So, suppose for all
. Let
. Then,
, which forces
, which implies
. Hence,
, and this completes our proof.
Note: If is finite, then
.
Lemma 2:
and
for all . (Here,
is the complement of
.)
Proof: The proof for each case is elementary.
Lemma 3: Suppose is finite. If
, then the characteristic function of
is
, i.e.
for all
.
Proof: Note the above is an extension of the third part of lemma . A simple induction on the number of subsets of
proves the result.
— Proof of the inclusion-exclusion principle —
Now, suppose are subsets of objects of type
, respectively. Observe that the set of objects that are NOT of type
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
. Using the first part of lemma
, we see that the characteristic function of this outside region is
, which from lemma
is the same as
.
Expand the last expression to get
.
Now, sum over all the elements of and use the second part of lemma
to obtain the desired result. And this completes our proof.
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: denotes the greatest integer less than
.
Ok, let’s now “build” the principle step by step.
1. Suppose there are objects out of which there are exactly
objects of type
. How many objects are NOT of type
? The answer is obvious:
. The Venn diagram below depicts the answer pictorially. The rounded rectangular region (with the orange border) is the set of all
objects, and the oval region (with the blue border) is the set of all
objects of type
. Then, the remaining white region that is outside the oval region denotes the set of all objects that are NOT of type
, and clearly, there are
of ‘em.

Indeed, let us take a simple example. Consider the set of first thirty natural numbers: . So,
. Now, out of these thirty integers, let
be the number of integers divisible by
. Then,
. It is easy to see that the number of integers NOT divisible by
equals
, which is what we would expect if we were to list all the integers not divisible by
. Indeed, those integers are
.
2. Now, suppose there are objects out of which there are exactly
objects of type
and
objects of type
. Also, suppose there are exactly
objects that are of both type
AND
. Then, how many objects are NOT of type
OR
? 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 . Now, one might be tempted to think that the number of objects inside the two oval regions is simply
. 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
counts
twice! And so, we must subtract
from the expression to get
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
, and we are done.
Continuing with our example used earlier, let be the number of integers divisible by
. Also, let
be the number of integers divisible by
AND
(i.e. we count multiples of
.) Now, note that
, and
.
Thus, using the formula derived above, the number of integers that are NOT divisible by OR
equals
. In fact, we can list these ten integers:
and
; and this confirms our answer.
3. Now, suppose there are objects out of which there are exactly
objects of type
,
objects of type
and
objects of type
. Also, let
denote the number of objects of type
AND
,
the number of objects of type
AND
,
the number of objects of type
AND
, and
the number of objects of type
AND
. Then, how many objects are NOT of type
OR
? 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 . 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
earlier. A brief thought will reveal that in the above expression, we have counted each of
and
twice and
thrice! To take care of this overcounting, we subtract each of
and
once from the expression, but in doing so, we also end up subtracting
thrice! We thus need to add
back into the expression to get
, 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
. And, we are done.
Again, continuing with our earlier example, let denote the number of integers divisible by
. Then,
. Also, let
denote the number of integers divisible by
AND
(i.e. we are counting multiples of
); then,
. Again, let
denote the number of integers divisible by
and
; then
. And, finally, let
denote the number of integers divisible by
and
; then
.
So, the number of integers NOT divisible by OR
equals
. Indeed, those eight integers are
and
.
It isn’t very hard to deduce the formula for the general case when we have a set of objects, out of which there are
objects of type
,
objects of type
, 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.
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)
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
[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 (where
) is a holomorphic function, then
attains its maximal value on any compact
on the boundary
of
. (If
attains its maximal value anywhere in the interior of
, then

