OFFSET
1,1
COMMENTS
From Chai Wah Wu, Sep 21 2016: (Start)
Proof that a(n) = 9*a(n-1) - 8*a(n-2) for n > 3: Here x and y denote numbers with no zero decimal digits. Decompose a(n) as a(n) = b(n) + c(n) where b(n) is the numbers of pairs x > y such that x and y have the same number of digits and x + y = 10^n. Note that if n > 1 and x + y = 10^n, then x <> y. If x > y are pairs of numbers of n digits that add to 10^n, then prepending x with the digit 8 and y with the digit 1 creates a pair of numbers of n+1 digits that add to 10^n. Similarly if we prepend x with 1 and y with 8.
We can also prepend the pairs of digits (7,2), (6,3) and (5,4) to x and y and to y and x. All pairs that contribute to b(n+1) can be constructed this way. This means that b(n+1) = 8*b(n) for n > 1.
Similarly prepending the digit 9 to x or y will result in a pair of numbers with n + 1 and n digits respectively that add to 10^(n+1). If x > y and x has n digits and y has < n digits with x + y = 10^n, then prepending the digit 9 to x results in a pair of numbers with n+1 and < n digits respectively that add to 10^(n+1). All pairs of numbers that contribute to the count c(n+1) can be constructed this way. This means that c(n+1) = 2*b(n) + c(n) for n > 1. Thus a(n+1) = b(n+1) + c(n+1) = 9*b(n) + b(n) + c(n) = 9*(a(n) - c(n)) + 8*b(n-1) + 2*b(n-1) + c(n-1) = 9*a(n) - 9*(2*b(n-1)+c(n-1)) + 10*b(n-1) + c(n-1) = 9*a(n) - 8*b(n-1) - 8*c(n-1) = 9*a(n) - 8*a(n-1).
The reason the recurrence relation a(n) = 9*a(n-1) - 8*a(n-2) fails for n = 3 is because for n = 1 there are two numbers, 5 and 5, which sums to 10, but they are equal to each other. This pair does not contribute to b(1), but they can be used to construct pairs in the counts b(2) and c(2).
In particular, for b(2) we have the pairs (85, 15), (75, 25), (65, 35), (55, 45) and for c(2) we have the pair (95,5). Thus these extra pairs results in b(2) = 8*b(1) + 4 and c(2) = 2*b(1) + c(1) + 1.
(End)
LINKS
Chai Wah Wu, Table of n, a(n) for n = 1..500
Index entries for linear recurrences with constant coefficients, signature (9,-8).
FORMULA
From Chai Wah Wu, Sep 19 2016: (Start)
a(n) = 9*a(n-1) - 8*a(n-2) for n > 3.
G.f.: x*(-4*x^2 + 9*x + 4)/((x - 1)*(8*x - 1)). (End)
a(n) = 9*(9*8^n-16)/112 for n>1. - Colin Barker, Sep 22 2016
E.g.f.: (63 - 144*exp(x) + 81*exp(8*x) - 56*x)/112. - Stefano Spezia, Nov 16 2022
EXAMPLE
10 = 1 + 9 = 2 + 8 = 3 + 7 = 4 + 6 making 4 different pairs, thus a(1) = 4.
MAPLE
P:=proc(n)local i, j, k, ok, count; count:=0; for i from 1 by 1 to n/2-1 do ok:=0; k:=i; while k>0 do j:=frac(k/10)*10; if j=0 then ok:=1; fi; k:=trunc(k/10); od; k:=n-i; while k>0 do j:=frac(k/10)*10; if j=0 then ok:=1; fi; k:=trunc(k/10); od; if ok=1 then count:=count+1; fi; od; print(n/2-1-count); end: P(1000);
MATHEMATICA
Table[Function[n, Length@ DeleteCases[Transpose@ {#, n - #}, w_ /; Or[MatchQ @@ w, Total@ Boole@ Map[DigitCount[#, 10, 0] > 0 &, w] > 0]] &@ Range@ Floor[n/2]][10^n], {n, 6}] (* Michael De Vlieger, Sep 19 2016 *)
LinearRecurrence[{9, -8}, {4, 45, 369}, 30] (* Harvey P. Dale, Nov 05 2023 *)
PROG
(PARI) nonzerodigits(n)=while(n, if(n%10, n\=10, return(0))); 1
a(N)=N=10^N; sum(n=1, N/2-1, nonzerodigits(n)&nonzerodigits(N-n))
(PARI) Vec(x*(-4*x^2 + 9*x + 4)/((x - 1)*(8*x - 1)) + O(x^30)) \\ Colin Barker, Sep 22 2016
CROSSREFS
KEYWORD
nonn,base,easy
AUTHOR
Paolo P. Lava and Giorgio Balzarotti, Apr 10 2006
EXTENSIONS
Extension, new description and program from Charles R Greathouse IV, Aug 05 2010
a(9)-a(13) from Donovan Johnson, Aug 27 2010
More terms from Chai Wah Wu, Sep 22 2016
STATUS
approved