OFFSET
1,1
COMMENTS
We calculate the number of integers between 1 and 10^n - 1 having k zeros in their decimal representation. To form a such number consisting of m digits (k < m), place k zeros in m-1 possible positions, then we must choose m-k digits different from zero. Thus, the number of integers between 1 and 10^n - 1 having k zeros in their decimal representation is: Sum_{m=k+1..n} binomial(m-1, k)*9^(m-k).
Hence the sum: Sum_{m=1..n} Sum_{k=0..m-1} binomial(m-1,k)*9^(m-k)*2^k = Sum_{m=1..n} 9^m*(11/9)*(m-1) = (9/10)*(11^n - 1).
LINKS
Colin Barker, Table of n, a(n) for n = 1..950
Index entries for linear recurrences with constant coefficients, signature (12,-11).
FORMULA
a(n) = (9/10)*(11^n-1) = 9*A016123(n-1).
From Vincenzo Librandi, Feb 15 2016: (Start)
G.f.: (9*x)/((1-11*x)*(1-x)).
a(n) = 11*a(n-1) + 9. (End)
E.g.f.: 9*exp(x)*(exp(10*x) - 1)/10. - Stefano Spezia, Sep 13 2023
EXAMPLE
a(1) = 9 because 2^f(1) + 2^f(2) + ... + 2^f(9) = 2^0 + 2^0 + ... + 2^0 = 9;
a(2) = 108 because 2^f(1) + 2^f(2) + ... + 2^f(99) = 9*10 + 2*9 = 108, where f(10) = f(20) = ... = f(90) = 1 and f(i) = 0 otherwise.
MAPLE
for n from 1 to 100 do: x:=(9/10)*(11^n-1):printf(‘%d, ‘, x):od:
MATHEMATICA
Table[Table[(9/10) (11^n - 1), {n, 1, 20}]] (* Bruno Berselli, Feb 15 2016 *)
CoefficientList[Series[9/((1 - 11 x) (1 - x)), {x, 0, 33}], x] (* Vincenzo Librandi, Feb 15 2016 *)
PROG
(Magma) [(9/10)*(11^n-1): n in [1..20]]; // Vincenzo Librandi, Feb 15 2016
(PARI) Vec(9*x/((1-11*x)*(1-x)) + O(x^30)) \\ Colin Barker, Feb 22 2016
CROSSREFS
KEYWORD
nonn,base,easy
AUTHOR
Michel Lagneau, Feb 14 2016
EXTENSIONS
Name edited by Jon E. Schoenfield, Sep 13 2017
STATUS
approved