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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum