Newsgroups: rec.puzzles
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Date: 10 Jan 91 18:23:01 GMT
Subject: Re: Numbers from 1 to 1,000,000 (corrected)

je...@essex.ac.uk (Reid J) writes:

>If p(n) is the number of zeros used in the range 1 - 10^n
>then
>    p(n) = p(n-1) + 9 * 10^(n-2) + 1  for n > 1 and p(1) = 1
>(Note I haven't prooved [sic] this yet....)

Wrong, presumably from carelessness rather than misunderstanding, and
don't think I'm throwing any stones.

In the numbers from 10^(n-1) through 10^n - 1, there are 9 * 10^(n-1)
numbers of n digits each, so 9(n-1)10^(n-1) non-leading digits, of
which one tenth, or 9(n-1)10^(n-2), are zeroes.  When we change the
range to 10^(n-1) + 1 through 10^n, we remove 10^(n-1) and put in
10^n, gaining one zero, so

  p(n) = p(n-1) + 9(n-1)10^(n-2) + 1 with p(1)=1.

Solving the recurrence yields the closed form

  p(n) = n(10^(n-1)+1) - (10^n-1)/9.

Dan