5
$\begingroup$

How many base $10$ numbers are there with $n$ digits and an even number of zeros?

Solution:

Lets call this number $a_n$.

This is the number of $n-1$ digits that have an even number of zeros times $9$ possibilities for the $n$th digit + number of $n-1$ digits that have an odd number of zeros and a zero for the $n$th digit.

$a_n = 9a_{n-1} + (10^{n-1} - a_{n-1})$

$a_n = 8a_{n-1} + 10^{n-1}$

We define

$a_0 = 1$

$a_1 = 9$

The generating function is

$G(x) = 1 + 9x + 82x^2 + 756x^3 + \cdots $

$G(x) = \sum_{n=0}^{\infty}a_n x^n$

$$\begin{align} G(x) - 1 & = \sum_{n=1}^{\infty} ([8a_{n-1} + 10^{n-1}] x^n)\\ & = \sum_{n=1}^{\infty} 8a_{n-1}x^n + \sum_{n=1}^{\infty}10^{n-1}x^n\\ & = 8x\sum_{n=1}^{\infty} a_{n-1}x^{n-1} + x\sum_{n=1}^{\infty}10^{n-1}x^{n-1}\\ & = 8x\sum_{n=0}^{\infty} a_{n}x^{n} + x\sum_{n=0}^{\infty}10^{n}x^{n}\\ & = 8x G(x) + x\left(\frac{1}{1-10x}\right) & \end{align} $$

$(1-8x)G(x) = x\left(\frac{1}{1-10x}\right) + 1$

$G(x) = \frac{1-9x}{(1-8x)(1-10x)}$

$G(x) = \frac{1/2}{1-8x} + \frac{1/2}{1-10x}$

$\therefore$ $a_n=\frac{1}{2}(8^n+10^n)$

Is this solution/method valid?

Note that the way i have set up the solution, and defined $a_0$ and $a_1$, there are supposed to be $82$ numbers in $a_2$. I am including the $0$ numbers of zeros, i.e. there are $9 \times 9 = 81$ numbers with $0$ zeros and $1$ number $00$.

$\endgroup$
2
  • $\begingroup$ The final expression is correct (I did it in a somewhat different way, going to a second order recurrence and using characteristic polynomial). $\endgroup$ Mar 29, 2016 at 20:56
  • $\begingroup$ @AndréNicolas Thanks André! $\endgroup$
    – JKnecht
    Mar 29, 2016 at 20:58

1 Answer 1

2
$\begingroup$

Here's another solution: clearly the number of $n$-digit numbers with $k$ zeroes is $f(n,k) = {n \choose k} 9^k$. Then we have

$$f(n,0) + f(n,1) + \cdots + f(n,n) = \sum_{k=0}^n {n \choose k} 9^k$$

and by the binomial theorem this is $(9+1)^n = 10^n$. On the other hand,

$$f(n,0) - f(n,1) + \cdots + (-1)^n f(n,n) = \sum_{k=0}^n {n \choose k} 9^k (-1)^k$$

and this is, again by the binomial theorem, $(9-1)^n = 8^n$. Adding the two equations together, we get

$$2 f(n,0) + 2 f(n,2) + \cdots + 2 f(n, n) = 8^n + 10^n$$

if $n$ is even, and

$$2 f(n,0) + 2 f(n,2) + \cdots + 2 f(n, n-1) = 8^n + 10^n$$

if $n$ is odd. Dividing through by 2 gives the result.

To be fair, this solution is not the first one that springs to mind unless you know the answer in advance.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .