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$
  • $\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$ – André Nicolas Mar 29 '16 at 20:56
  • $\begingroup$ @AndréNicolas Thanks André! $\endgroup$ – JKnecht Mar 29 '16 at 20:58
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.