The Art and Craft of Problem Solving

348 CHAPTER 9 CALCULUS

Determine, with proof, the largest number that is the product of positive

integers whose sum is 197 6.

Partial Solution: Once again, we shall inappropriately apply calculus to a discrete

problem. It makes intuitive sense for the numbers whose sum is 1976 to be equal (see

the discussion of the AM-GM inequality in Section 5.5). But how large should these

parts be? Consider the optimization question of finding the maximum value of

where S is a positive constant. An exercise in logarithmic differentiation (do it!) shows

that S / x = e. Thus, if the sum is S each part should equal e and there should be S / e

parts.

Now this really makes no sense if S = 1976 and the parts must be integers, and

having a non-integral number of parts makes even less sense. But it at least focuses

our attention on parts whose size is close to e =^2. (^71828). ... Once we start looking
at parts of size^2 and 3, the problem is close to solution (use an algorithmic approach
similar to our proof of the AM-GM inequality).
The next example, due to Euler, is a generatingfunctionological proof of the infini­
tude of primes. The argument is interesting and ingenious and has many applications
and generalizations (some of which you will see in the problems and exercises below).
It can be rigorized pretty easily by considering partial sums and products, but that
obscures the inspiration and removes the fun.
Example 9.4.7 Prove that the number of primes is infinite.
Solution: Consider the harmonic series
1 1 1 1
1+
"2

• 3


• 
  

  4

  
  


• 
  

  :5
  +····
  Let us try to factor this sum, which doesn't really make sense, since it is infinite. Define
  1 1 1
  Sk := 1 + k +
  k^2

  
  


• 
  

  k^3

  
  


• ... ,
  and consider the infinite product
  S 2 S 3 SSS 7 S 11 ... ,
  where the subscripts run through all primes. The first few factors are

(1 +!+�+ ... ) (1+!+�+ ... ) (1+!+�+ ... ) ...

2 2^2 3 32 5 52

.

When we expand this infinite product, the first few terms will be

1 1 1 1 1

1+"2+

3

+ 4 +

:5

+

"6

+···'

and we realize that for each n, the term 1 / n will appear. For example, if n = 360, then

l/n will appear when we multiply the terms 1/2^3 , 1/3^2 , and 1 /5. Moreover, l/n will