Hey, I need a little help:
Solve this with recurrence equations: One string with decade digits is valid only if the string consists even number of zeros. How many valid words with length n are there?
Thank you.
neat problem.
Suppose you've got a $k$ digit string
There are $v_k$ valid strings and $10^k-v_k$ invalid strings.
We select the $k+1$th digit, $d_{k+1}$
If $d_{k+1}=0$ then adding this to all the currently invalid strings makes them valid.
Similarly if $d_{k+1}\neq 0$ then adding this to all the currently valid strings keeps them valid.
so we have
$v_{k+1} = 9 v_k + (10^k-v_k) = 8v_k + 10^k$
there are $9$ valid strings of length $1$ so $v_1 = 9$
and this completes the recursion equation.
a bit of toying with this reveals
$v_n = 9 \cdot 8^{n-1} + \displaystyle \sum_{k=2}^n 8^{n-k}\cdot 10^{k-1} =
9\cdot 8^{n-1}-2^{n-3} \left(5\cdot 2^{2 n}-4\cdot 5^n\right)$
Decade digits are $\displaystyle \{0,1,2,...,9\}$?
If you wish to find $\displaystyle c(n)$ the count of words length $\displaystyle n$, you can consider how such words can be made from those of length $\displaystyle (n-1)$ (you must add a non-zero digit) and from those of length $\displaystyle (n-2)$ (by adding two zeros). You thus get an expression of the form
where $\displaystyle A$ and $\displaystyle B$ are either constants or expressions in $\displaystyle n$
$\displaystyle c(n) = A c(n-1) + Bc(n-2)$
The trick is to avoid double counting. This is why from words of length $\displaystyle (n-2)$ we only look at adding two zeros, because if we add two non-zeros, we pass through the $\displaystyle (n-1)$ case on the way to words of length $\displaystyle n$.