Pseudo-Random Function families whose instances have full domain
Here is a proof sketch of the security of your construction.

Let $G: \{0,1\}^k \to \{0,1\}^{3k}$ be the PRG and let $G_0, G_1, G_2$ denote the first, middle, and last third of the output of $G$.

Define the function $F_{x,m}$ as follows:

$\qquad
F_{x,m}(y) =
  \begin{cases}
    rand &amp; \mbox{ if } y&lt;x \mbox{ in lex order} \\
    G_m( rand ) &amp; \mbox{ if } y=\epsilon \\
    G_m( F_{x,b}(y&#39;) ) &amp; \mbox{ if } y=y&#39;b \\ 
\end{cases}$

Here $rand$ denotes a value chosen at random for each $(y,m)$, independent of everything else.

Now $F_{\epsilon,2}$ is your GGM construction instantiated with a random seed. Suppose we picture the GGM construction as a labeling of the edges and vertices of a binary tree. Each vertex is associated with a finite binary string. Each vertex labels its two outgoing edges $G_0(\ell), G_1(\ell)$  and labels itself $G_2(\ell)$, where $\ell$ is the value assigned to its incoming edge. Then $F_{x,2}$ is the result of having vertices $y &lt; x$ assign their relevant labels totally randomly.

Fix an adversary $A$ with running time $p(\cdot)$, to which we give oracle access to a function of this form. We'll consider the sequence of hybrids $F_{\epsilon,2}, F_{0,2}, F_{1,2}, F_{00,2}, \ldots, F_{\omega,2}$, where $|\omega| &gt; p(k)$.  From $A$'s point of view, $F_{\omega,2}$ has output distributed identically to a totally random function.

If $x$ is the successor of $x&#39;$ in lex order, then $F_{x,2}$ and $F_{x&#39;,2}$ differ only in one application of the PRG. Thus, successive hybrids are indistinguishable. However, we've proposed an exponential number of hybrids, so we are not yet done! Intuitively $A$ can only "notice" the changes in a polynomial-sized portion of the tree. We formalize this as follows:

Conditioned on the event that $A$ never queries its oracle on a string beginning with $x$, then $F_{x,2}$ and $F_{x&#39;,2}$ give identical output distribution. Let $q_x$ denote the probability that $A$ queries its oracle on such a string, and let $\delta(\cdot)$ denote the negligible security error of the PRG. Then we have:

$\qquad\Big|\Pr[A^{F_{x,2}}(1^k) = 1] - \Pr[A^{F_{x&#39;,2}}(1^k) = 1] \Big| \le q_x \delta(k)$

Then by a hybrid argument, we have:

$\qquad\Big|\Pr[A^{F_{\epsilon,2}}(1^k) = 1] - \Pr[A^{F_{\omega,2}}(1^k) = 1] \Big| \le \delta(k)\sum_x q_x$

The first expression involves $A$ with oracle access to the GGM function, and the second expression involves $A$ with oracle access to a random function. Now we bound the sum $\sum_x q_x \le p(k)^2$. Since $\delta(k) p(k)^2$ is negligible, the construction is a PRF.