[jualme]

El problema dice que:

Un sistema de identificación considera válida una cadena de dígitos si contiene un número par de ceros. por ejemplo 1230407869 es válida, mientras que 120987045608 no lo es. Sea a_n el número de cadenas válidas de longitud n. Encuentre una relación de recurrencia para a_n.

Mi problema es que llegué a que la fórmula recurrente sería a_n=9n(a_n-1) con a_1= 0, a_2=1 y n\geq{3} pero en esa fórmula no se contempla que cuando n es par tengo una cadena más válida y cuando n es impar no tengo esa cadena no he logrado solucionar esa parte. ¿Me pueden ayudar?

[Juan Pablo Sancho]

Bienvenido Jualme.
Haciendo uso de binomiales.

Para \(  n  \) tenemos \(  n = 2\cdot p + r  \) donde \(  r \in \{0,1 \}  \).

\(  \displaystyle a_n = \sum_{i=1}^p { n \choose 2i } = \sum_{i=1}^p { n - 1 \choose 2i } + \sum_{i=1}^p { n - 1 \choose 2i - 1} =  \)

\(  \displaystyle = \sum_{i=1}^{n-1} { n-1 \choose i} = 2^{n-1} - 1  = 2 \cdot 2^{n-2}+( 1- 2 ) = 2\cdot[2^{n-2} - 1] + 1 = 2\cdot a_{n-1} + 1   \)   

Creo que también podría servir:

\(  \displaystyle a_n=a_{n-1}+(n-1) \). con \( a_1=0 \)

Si tienes cualquier duda pregunta.

Mañana lo repasaré.