Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search