Counting numbers with the digit 5: How to express recurrence relation in closed form? I figured out the algorithm for finding the count of numbers containing the digit 5 for any power of 10.
What is the correct way to express y in this formula?

$f(x) = 9y + (x/10)$
Where y is the previous result and x is the power of 10 we're checking against.
i.e. $y = 1$ and $x = 100$, or $y = 19$ and $x = 1000$, etc.

For example:
$f(1000) = 9*f(100) + (1000/10)$
and continue recursing until $f(10)$.
I'm a programmer, not a mathematician, so I don't know how to properly express this.
 A: What you're saying is that $f(x)$ is the number of positive integers with a $5$ in them that are smaller than $x$. You then claim:
$$f(10^n) = 9f(10^{n-1}) + \frac {10^n} {10} = 9f(10^{n-1}) + 10^{n-1}$$
That technically answers your question "what is the correct way to express $y$?", but I'm not sure that's what you meant to ask.
Your formula is indeed correct, incidentally, and can be easily proven by the following argument. $f(10^n)$ is just the number of $n-1$-digit numbers with a $5$ in them. Take any $n-2$ digit number with a $5$ in it, and you can use it to get $9$ $n-1$ digit numbers with a $5$ in them by simply putting a $0$, $1$, $2$, $3$, $4$, $6$, $7$, $8$ or a $9$ in front of it. So that gives us $9f(10^{n-1})$ possibilities, but we haven't covered $n-1$ digit numbers that start with a $5$. There are $10^{n-1}$ of those, and they all obviously have a $5$ in them, so in total we have $f(10^n)=9f(10^{n-1})+10^{n-1}$, as claimed.
The recurrence relation can in fact be solved for an explicit formula for $f$. To abbreviate, let $a_n=f(10^n)$, so:
$$a_0=0$$
$$a_n=9a_{n-1}+10^{n-1}$$
Let $\delta_n=a_n-9a_{n-1}=10^{n-1}$ for $n\geq1$. We can get $a_n$ from the $\delta_i$s, for example:
$$a_3=\delta_3+9a_2=\delta_3+9(\delta_2+9a_1)=\delta_3+9\delta_2+9^2a_1=\delta_3+9\delta_2+9^2\delta_1$$
The pattern is obvious, and we can prove by induction that $a_n=\sum^n_{i=1}\delta_i9^{n-i}=\sum^n_{i=1}10^{i-1}9^{n-i}$ (remember that $\delta_i=10^{i-1}$). Now it's just algebra:
$$a_n=\sum^n_{i=1}10^{i-1}9^{n-i}=\frac{9^n}{10}\sum^n_{i=1}10^{i}9^{-i}=\frac{9^n}{10}\sum^n_{i=1}\left(\frac{10}{9}\right)^i=\frac{9^n}{10}\left(\frac{(\frac{10}{9})^{n+1}-1}{\frac{10}{9}-1} - 1\right)$$
In the last step I applied the formula for a geometric sum.
You can simplify this a little bit with more algebra:
$$a_n=\frac {10^{n+1} - 9^{n+1} - 9^n} {10}=10^n - \frac {9^{n+1}+9^n} {10}=10^n - \frac {9^n(9+1)} {10}=10^n - 9^n$$
(For the sake of humility, I'll just note that I had to consult the OEIS before spotting that very last simplification) This is a better formula if we're talking about computers, since it doesn't require floating points. Whether it's faster than your recursive formula I don't know, but it's interesting nonetheless.
A: Here's a simple way to arrive at @JackM's closed-form expression:


*

*$10^n$ = the count of all numbers up to $n$ digits

*$9^n$ = the count of all numbers up to $n$ digits that don't contain 5 anywhere

