
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.

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.
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*}
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} $$