1. ## recurrence equations

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.

2. ## Re: recurrence equations

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

3. ## Re: recurrence equations

Decade digits are $\{0,1,2,...,9\}$?

If you wish to find $c(n)$ the count of words length $n$, you can consider how such words can be made from those of length $(n-1)$ (you must add a non-zero digit) and from those of length $(n-2)$ (by adding two zeros). You thus get an expression of the form

$c(n) = A c(n-1) + Bc(n-2)$
where $A$ and $B$ are either constants or expressions in $n$

The trick is to avoid double counting. This is why from words of length $(n-2)$ we only look at adding two zeros, because if we add two non-zeros, we pass through the $(n-1)$ case on the way to words of length $n$.