How to determine recurrence relation for $n$-number sequence such that even numbers are not contiguous out of $x$ total numbers? 
Let $x\ge 1, x \in \mathbb N$ and let $t(n)$ be the number of sequences of length $n$ such that their elements belong to the set $\{0,1,2,...,2x\}$. In the sequences, contiguous occurrences of even numbers are forbidden.
For example for $x=5, n=4$:
1,4,7,9 is a valid sequence
1,2,4,7 is not a valid sequence

I need to find the recurrence relation for such sequence and to solve the characteristic equation for the recurrence.
If the first number in the sequence is odd the next number can be even or odd, thus $t_{odd}(n)=t_{odd}(n-1)+t_{even}(n-1)$.
If the first number is even the next number must be odd thus: $t_{even}(n) = \frac{x}{2}t_{even}(n-2)+\frac{x}{2}t_{odd}(n-2)$ because the next number must be one of $\frac{x}{2}$ odd numbers.
I'm not sure if I'm on the right track and if I am I don't understand how to combine the two cases in order to solve the characteristic equation.
 A: You're on the right general track, but there are some small algebraic mistakes.
First, note that the number of odd digits (or the number of even digits) is $x$, not $x/2$, since the total number of digits is $2x$; basically, the division by 2 that you're using in your current (incorrect) formula for $t_{even}$ has already been 'baked in' for you. Likewise, the number of even digits is $x+1$ : $0, 2, \ldots, 2x$ (there's a sneaky off-by-one problem lurking here, one that I've made a couple of times already in this answer and its comments!)
Second and more critically, there are errors in both your terms because you're missing a factor of $x$.  In your $t_{odd}$ term, you're right about the ways it can break down but forgot that there can be $x$ different 'next digits'; you make the same mistake in your $t_{even}$ term, one layer removed. Try working through your tentative recurrences in the case $n=3, x=2$ (so there are 5 digits) to see what I mean. 
Once you take these factors into account, you'll have an expression for $t_{odd}(n)$ in terms of a constant factor times $(t_{odd}(n-1)+t_{even}(n-1))$, and likewise an expression for $t_{even}(n)$ in terms of a constant factor times $(t_{odd}(n-2)+t_{even}(n-2))$; now just add them, set $u(n)=t_{odd}(n)+t_{even}(n)$, and note that this lets you write $u(n)$ in terms of $u(n-1)$ and $u(n-2)$.
Note that you can get at the same result somewhat more directly; let $u(n)$ be the number of such strings with $n$ digits (i.e., $u(n)=t_{odd}(n)+t_{even}(n)$.) Then as you already noticed, if $u(n)$ begins with an odd digit, the rest of the sequence can be arbitrary, while if $u(n)$ begins with an even digit, the next digit must be odd but the rest can be arbitrary; in other words, $u(n) = \{\#$of ways the first digit can be odd$\}\cdot u(n-1)+\{\#$of ways the first digit can be even$\}\cdot\{\#$of ways the second digit can be odd$\}\cdot u(n-2)$, and all of the bracketed expressions should be easy.
