[Mailbag] What Do You Do with the Ideas You Used to Call “Mistakes”

Guillaume ParĂ©, in the very interesting comments of my last post where I
urged us to reconsider mistakes: I do agree with what is written, but I am
still w...
1 week ago
The answer is 97,038,694,279.
ReplyDeleteLet f(n) be the number of ndigit numbers (with leading zeros allowed) that contain two consecutive nines.
Let n>2 be given, and let S be the set of all ndigit numbers that contain two consecutive nines.
If an ndigit number starts with 99 then it belongs to S, and there are 10^(n2) such numbers.
The number of elements in S that begin with a single 9 is 9*f(n2), because there are nine choices for the second digit (08) and there are f(n2) ways to complete the remaining n2 digits.
The number of elements in S that do not begin with 9 is 9*f(n1), because there are nine choices for the first digit (08) and there are f(n1) ways to complete the remaining n1 digits.
Therefore f(n) = 9*f(n1) + 9*f(n2) + 10^(n2). We can use this recurrence to rapidly calculate f(12).
f(1) = 0
f(2) = 1
f(3) = 9*1+0+10 = 19
f(4) = 9*19+9*1+100 = 280
...
f(12) = 97,038,694,279