A268839 a(n) = Sum_{j=1..10^n-1} 2^f(j) where f(j) is the number of zero digits in the decimal representation of j.

9, 108, 1197, 13176, 144945, 1594404, 17538453, 192922992, 2122152921, 23343682140, 256780503549, 2824585539048, 31070440929537, 341774850224916, 3759523352474085, 41354756877214944, 454902325649364393, 5003925582143008332, 55043181403573091661

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

Cf. A016123, A033713, A033714, A055641, A119291.

Sequence in context: A080505 A104224 A099676 * A214668 A234467 A288550

Adjacent sequences: A268836 A268837 A268838 * A268840 A268841 A268842

Keyword

nonn,base,easy

Author

Michel Lagneau, Feb 14 2016

Extensions

Name edited by Jon E. Schoenfield, Sep 13 2017

Status

approved