This site is supported by donations to The OEIS Foundation.

Template:Sequence of the Day for May 18

From OeisWiki
Jump to: navigation, search

Intended for: May 18, 2013

Timetable

  • First draft entered by Alonso del Arte on March 23, 2012
  • Draft reviewed by Daniel Forgues on May 13, 2012
  • Draft approved by Daniel Forgues on May 17, 2015
Yesterday's SOTD * Tomorrow's SOTD

The line below marks the end of the <noinclude> ... </noinclude> section.



A016189:
10n  −  9n, n   ≥   0
.
{ 0, 1, 19, 271, 3439, 40951, 468559, 5217031, ... }
This sequence can also be computed using a recurrence relation:
a (0) = 0; a (n) = 9 a (n  −  1)  +  10n  − 1, n   ≥   1.
This shows that this sequence answers the question: “How many numbers in
{0, ..., 10n  −  1}
have at least one 9 among their digits?” Up to 9, there is of course just 9. Up to 99 we have 9, 19, 29, ..., 89 (that’s nine numbers) and 90, 91, 92, ..., 99 (that’s ten numbers). And up to 999, we have 900, 901, 902, ..., 999 (that’s a hundred numbers), and between each multiple of 100 to the next, up to 800, we have nineteen numbers with 9s among their digits, so we can just multiply the previous term by 9 rather than count these numbers one by one, hence the recurrence.

Of course this can also be used for how many numbers (base 10) in
{0, ..., 10n  −  1}
have at least one digit greater than or equal to
d, 0   ≤   d   ≤   9: 10n  −  d  n, n   ≥   0
. This should also work for how many numbers (base
b
) in
{0, ..., bn  −  1}
have at least one digit greater than or equal to
db, 0   ≤   db   ≤   b  −  1: bn  −  dbn, n   ≥   0
.

Now, for
n = 0
, i.e. how many numbers from 0 to 0 have at least one digit greater than or equal to 0: 10 0  −  9 0 = 1  −  1 = 0, which is correct when we consider that leading zeros are not normally written (we make an exception for zero, otherwise we would have the empty string...). Or, if you prefer, you may add a
0n
term to the formula, e.g.
10n  −  9n  +  0n, n   ≥   0,
to get 1 for
n = 0
. The recurrence would be slightly modified thus:
a (0) = 1; a (1) = 1; a (n) = 9 a (n  −  1)  +  10n  − 1, n   ≥   2
.