¿Cuántos números base$10$ hay con$n$ dígitos y un número par de ceros?

Question

Cuántos base $10$ números están ahí con $n$ dígitos y un número par de ceros?

Solución:

Permite llamar a este número $a_n$.

Este es el número de $n-1$ dígitos que tienen un número par de ceros veces $9$ posibilidades de la $n$th dígitos + número de $n-1$ dígitos que tienen un número impar de ceros y un cero para el $n$th dígitos.

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

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

Definimos

$a_0 = 1$

$a_1 = 9$

La generación de la función es

$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)$

Es esta la solución/método válido?

Tenga en cuenta que el camino que he de configurar la solución, y se definen $a_0$$a_1$, se supone que se $82$ cifras en $a_2$. Estoy incluyendo el $0$ números de ceros, es decir, hay $9 \times 9 = 81$ números con $0$ ceros y $1$$00$.

Answer 1

Aquí hay otra solución: claramente el número de $n$-números de dos dígitos con $k$ ceros es $f(n,k) = {n \choose k} 9^k$. Entonces tenemos

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

y por el teorema del binomio esto es $(9+1)^n = 10^n$. Por otro lado,

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

y este es, de nuevo por el teorema del binomio, $(9-1)^n = 8^n$. Sumando las dos ecuaciones, obtenemos

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

si $n$ es aún, y

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

si $n$ es impar. Dividiendo por 2 da el resultado.

Para ser justos, esta solución no es la primera que viene a la mente, a menos que usted sabe la respuesta por adelantado.