Finite Series and Greatest Integers

Date: 03/06/2003 at 06:15:08
From: John
Subject: Finite series and greatest integers

For n a positive integer, let t(n) denote the number of positive 
divisors of n (including n and 1), and let s(n) denote the sum of 
these divisors. Prove the following:

   t(1) + t(2) + ... + t(n) = [n/1] + [n/2] + ... + [n/n],
   s(1) + s(2) + ... + s(n) = [n/1] + 2[n/2] + ... + n[n/n],

where [r] denotes the greatest integer less than or equal to r.

I'm pretty sure this is a proof by induction, but I'm quite weak at 
these. Is there any other way to try and solve this?

Date: 03/07/2003 at 05:11:28
From: Doctor Jacques
Subject: Re: Finite series and greatest integers

Hi John,

I don't believe that induction would be a good method for this kind of 
problem. The point is that, in an inductive proof, you would have to 
relate [n/k] to [(n+1)/k] or [n/(k+1)] and this could be complicated. 
(However, this is not a general rule.)

In this case, there is a simple approach, which I will illustrate 
with the first example.

Let us imagine an n by n table, where we put a mark in cell (i,j) 
(row i, column j) whenever i is a divisor of j.

We want to compute the number of marks in the table in two different 
ways.

The number of marks in column j is the number of divisors of j, i.e.
t(j).

The number of marks in row i is the number of multiples of i between 
1 and n.

As an illustration, we will look at the table I mentioned for the 
case n = 7.

Here is the table:

    1  2  3  4  5  6  7   Total
 ------------------------------
  1|*  *  *  *  *  *  * |  7
  2|   *     *     *    |  3
  3|      *        *    |  2
  4|         *          |  1
  5|            *       |  1
  6|               *    |  1
  7|                  * |  1
 --+--------------------+------
   |1  2  2  3  2  4  2 | 16

In what follows, cell (i,j) means the cell in row i and column j (the 
row is first).

How did I build the table?

I put a star in cell (i,j) whenever i divides j. For example, there 
is a star in cell (2,6) because 2 divides 6.

The last column contains the number of stars in each row, and the 
last row contains the number of stars in each column.

Obviously, the total number of stars is the same, whether you count 
them by columns or by rows. That is exactly what we are going to do.

Consider first the columns. In a particular column 'j', the stars are 
in the rows 'i' such that i is a divisor of j. This means that the 
number of stars in column j is the number of divisors of j - this is 
what you called t(j). For example, look at column 6 - there are stars 
in rows 1, 2, 3, and 6 (these are the divisors of 6) and t(6) = 4.

As column j contains t(j) stars, the total number of stars in the 
table is the sum of the columns, i.e.

  t(1) + t(2) + ... + t(n)

Notice that this is the left-hand side of your equation.

Consider now the rows. Row 'i' contains a star in column j if i 
divides j, or j is a multiple of i. The stars in row i correspond to 
the multiples of i less than or equal to n (in this case, n=7).

How many multiples of i are there  between 1 and n?

Well, any multiple of i is of the form k*i, for a positive integer k. 
We must have:

  k*i <= n

   or

  k <= (n/i)

where k is an integer. This means that the largest value of k is the 
largest integer <= (n/i) - this is the definition of what you called 
[(n/i)].

The multiples of i are:

  i*1, i*2, .... i*[(n/i)]

and there are [(n/i)] of them; which means that there are [(n/i)] 
stars in row i.

We conclude that the total number of stars in the table is the sum of 
all the rows, i.e.

  [(n/1)] + [(n/2)] + ... + [(n/n)]

and this is the right-hand side of your equation.

As both methods of counting must yield the same result, you have 
proven your equation.

For the second problem, the method is similar. Instead of putting 
stars in the table, we put the row number - i.e. we put i in cell 
(i,j) if i divides j. After that, we compute the sum of all numbers 
in the table, first by columns, and then by rows, and compare the 
results.

Does this make sense?

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/