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 ?
If you wish to find the count of words length , you can consider how such words can be made from those of length (you must add a non-zero digit) and from those of length (by adding two zeros). You thus get an expression of the form
where and are either constants or expressions in
The trick is to avoid double counting. This is why from words of length we only look at adding two zeros, because if we add two non-zeros, we pass through the case on the way to words of length .