How to solve those recurrences with generating functions? 
I know we can solve these recurrences with generating functions, but I'm not familiar with that, so I hope there is a detailed solution for the problem.
 A: Let $q(x)=\sum_nQ_nx^n$ and $r(x)=\sum_nR_nx^n$. Then summing the left-hand recurrence from $1$ to $\infty$ gives
$$
q=2xr+\frac x{1-x}\;,
$$
and summing the right-hand recurrence from $1$ to $\infty$ gives
$$
r=q+xq+\frac x{1-x}\;.
$$
Substituting the second equation into the first yields
$$
q=2xq+2x^2q+\frac{2x^2}{1-x}+\frac x{1-x}\;,
$$
with solution
$$
q=\frac{x(1+2x)}{(1-x)(1-2x-2x^2)}\;.
$$
Then substituting that into the second equation yields
$$
r=\frac{x(1+x)}{(1-x)(1-2x-2x^2)}\;.
$$
As wj32 rightly pointed out, we can use partial fractions to obtain the coefficients in closed form. Factoring $1-2x-2x^2$ as $(1-(1-\sqrt3)x)(1-(1+\sqrt3)x)$ we get
$$
q=x\left(\frac{1-2/\sqrt3}{1-(1-\sqrt3)x}+\frac{1+2/\sqrt3}{1-(1+\sqrt3)x}-\frac1{1-x}\right)
$$
and thus
$$
\begin{align}
Q_n&=\left(1-\frac2{\sqrt3}\right)(1-\sqrt3)^{n-1}+\left(1+\frac2{\sqrt3}\right)(1+\sqrt3)^{n-1}-1
\\
&=\frac{(1+\sqrt3)^{n+1}-(1-\sqrt3)^{n+1}}{2\sqrt3}-1
\end{align}
$$
for $n\ge1$, and
$$
\begin{align}
R_n&=Q_n+Q_{n-1}+1\\
&=\frac{(2+\sqrt3)(1+\sqrt3)^n-(2-\sqrt3)(1-\sqrt3)^n}{2\sqrt3}-1\\
&=\frac{(1+\sqrt3)^{n+2}-(1-\sqrt3)^{n+2}}{4\sqrt3}-1\;.
\end{align}
$$
A: This the problem 1.10 in Knuth's book "Concrete Mathematics".
I give a solution for $Q_n$ using Knuth's notations.
First we have
$$Q_n=\left\{\begin{array}{ll}0,&n\leq0\\1,&n=1\\2Q_{n-1}+2Q_{n-2}+3,&n\geq2\end{array}\right.$$
So in general, we have
$$Q_n=2Q_{n-1}+2Q_{n-2}+3[n\geq2]+[n=1]$$
Suppose $q(z)$ is the generating function, re-writing the recurrence, we have
$$q(z)=2z\cdot q(z)+2z^2\cdot q(z)+\frac{3z^2}{z-1}+z$$
Solving for $q(z)$, we obtain
$$q(z)=\frac{u(z)}{v(z)}=\frac{z+2z^2}{(1-z)(1-2z-2z^2)}=\frac{z+2z^2}{(1-z)[1-(1+\sqrt{3})z][1-(1-\sqrt{3})z]}$$
According to Theorem (7.29) in "Concrete Mathematics", if we have $q(z)=u(z)/v(z)$, and $v(z)=\rho_0(1-\rho_1z)\ldots(1-\rho_lz)$, and $\rho_1,\ldots,\rho_l$ are distinct, and $u(z)$ is a polunomial of degree less than $l$, then
$$Q_n=[z^n]q(z)=a_1\rho_1^k+\cdots+a_l\rho_l^k$$
where
$$a_k=\frac{-\rho_ku(1/\rho_k)}{\frac{d}{dz}v(1/\rho_k)}$$
Applying this theorem, we get $\rho_1=1$, $\rho_2=1+\sqrt{3}$, $\rho_3=1-\sqrt{3}$ and $a_1=-1$, $a_2=\frac{3+\sqrt{3}}{6}$, $a_3=\frac{3-\sqrt{3}}{6}$
So we have
\begin{eqnarray*}
Q_n &=& a_1\rho_1^k+a_2\rho_2^k+a_3\rho_3^k\\
&=&\frac{3+\sqrt{3}}{6}(1+\sqrt{3})^n+\frac{3-\sqrt{3}}{6}(1-\sqrt{3})^n-1\\
&=&\frac{(1+\sqrt{3})^{n+1}-(1-\sqrt{3})^{n+1}}{2\sqrt{3}}-1
\end{eqnarray*}
