Inhomogeneous recurrence relation: $x(n) = 2x(n-1)+(n\bmod 2)$

Question

How can I solve a recurrence relation given as $$x(n)=\begin{cases} 2 x(n-1)+1 &n=\text{odd}\\2 x(n-1) & n=\text{even}\end{cases}$$ I know how to solve them individually,$x(n)=a(2^n)$,where $a$=constant (for homogenous part) and $x(n)$=some constant (for non-homogenous part);ie total solution is $$x(n)=a.2^n+b$$ $a$,$b$ constants. But how to combine them together to find an integrated solution? Please help. The solution has been given as:$x(n)=(2/3) 2^n-(1/6)(-1)^n-(1/2)$

Answer 1

The inhomogeneous part is not a constant. The recurrence is

$$x_n - 2 x_{n-1} = \frac{1}{2} [1-(-1)^n]$$

Therefore the inhomogeneous solution $x_n^{(I)}$ is of the form $A + B (-1)^n$. Substitute that into the equation and determine $A$ and $B$.