Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Counting > Adding Two Ways

A clever trick mathematicians use is to add things up two different ways.  In particular, I've noticed several seemingly different areas of math where a quantity can be represented on a two-dimensional grid, and then the value can be sliced vertically, and added, or it can be sliced horizontally and added.  In these cases, the trick is either to equate these two ways of adding the quantities, or to show the two areas add up to the whole rectangle.  A few examples will make clear what I mean.

Examples of adding things in two ways

 . . . . . .

1. The Sum of Totients of Divisors of n is n (Euler's Totient Function)

2a. Young's Inequality, the general form . . . . . .

2b. the related discrete form (The Nondecreasing Sequence Two puzzle whose most elegant solution relies on Young's Inequality), involving nondecreasing positive integer sequences.

2c. The Integration by Parts formula is another example, closely related to the integral form of Young's Inequality -- to make the similarity clear, express it as

∫u dv + ∫v du = uv,

and treat u and v as functions of an independent parameter, t.  Now, plot the locus of (u,v) on axes, (u horizontal, v vertical), and it becomes clear that the area, uv, is composed of the sum of the two integrals, as each one views the area "under" the curve as being between the curve and its axis.  That is, ∫v du represents the area between the curve and the u axis, while ∫u dv represents the area between the curve and the v axis.

3.  Conjugate partitions (as visualized using Ferrers Diagrams) give us a way to get the same number of partitions for two different questions, e.g.

3a. Number of partitions of n into at most 3 parts;
3b. Number of partitions of n in which the greatest part is at most 3;

The conjugate of each partition counted in 3a is counted in 3b.

3c. Number of partitions of n+3 into exactly 3 parts;
3d. Number of partitions of n+3 in which the greatest part is 3;

Similarly, the conjugate of each partition counted in 3c is counted in 3d.  Moreover, the number of partitions counted in 3a, 3b, 3c, and 3d are all the same for any given n.  (To see that every partition counted by 3a is counted by 3c, add 1+1+1 to each partition found by 3a.  For the inverse, subtract 1+1+1 from each partition found by 3c, causing the parts to disappear if they were 1.)

4. Back to number theory: sum(k=1 to n) tau(k) = sum(h=1 to n) [n/h], where tau(n) is the number of positive divisors of n. (Tau function: number of divisors)

 

Related pages in this website

 . . . . . .

Euler's Totient Function has a section that proves: The Sum of Totients of Divisors of n is n.

Young's Inequality -- Let f be a real-valued, continuous, and strictly increasing function on [0,c] with c > 0. If f(0)=0, a in [0,c], and b in [0,f(c)], then

\[\int_0^af(x)dx+\int_0^bf^{-1}(y)dy\ge ab,\]

The Nondecreasing Sequence Two puzzle uses a discrete form of Young's Inequality.

The Integration by Parts formula adds up the area, uv, a second way: ∫u dv + ∫v du

 . . . . . . a page is needed to describe conjugate partitions (as visualized using Ferrers Diagrams), and then it will be linked here.  Also, this page should have a methodology for finding the number of partitions where the parts have certain properties, e.g. odd numbers, prime numbers, or almost hilariously: partition numbers themselves!

Tau function: τ(n) is number of positive divisors of n.

 


The webmaster and author of this Math Help site is Graeme McRae.