The recursion relation is $$ \mathbf{F_{n+1}} = \mathbf{M}\mathbf{F_n} \;\mathrm{where}\; \mathbf{M} = \left( \begin{array}{rr}10 & 1\\ 0 & 9\end{array} \right). $$ Life is easier if we start the recursion with $$ \mathbf{F_0} = \left( \begin{array}{l}0\\1\end{array} \right) $$

```
In [x]: M = np.matrix([[10, 1], [0, 9]])
In [x]: F0 = np.matrix([[0], [1]])
In [x]: print(M * F0) # ie F1
[[1]
[9]]
```

To find the number of numbers containing 5 less than $10^{10}$, simply apply the recursion relation 10 times to $\mathbf{F_0}$:

```
In [x]: print(M**10 * F0)
[[6513215599]
[3486784401]]
```

That is, there are 6,513,215,599 positive integers less than 10,000,000,000 which contain the digit 5.

For a more direct solution, observe that the number of numbers $<10^n$ which *do not* contain a 5 is $9^n$ (since there are 9 ways to choose each digit out of the 10 available, including 0), so there are $10^n - 9^n$ numbers which do contain a 5:

```
In [x]: for n in range(1,11):
...: pn = (M**n * F0)[0]
...: print(pn, pn == 10**n - 9**n)
...:
[[1]] [[ True]]
[[19]] [[ True]]
[[271]] [[ True]]
[[3439]] [[ True]]
[[40951]] [[ True]]
[[468559]] [[ True]]
[[5217031]] [[ True]]
[[56953279]] [[ True]]
[[612579511]] [[ True]]
[[6513215599]] [[ True]]
```