Typesetting a pattern matching equation

Without an image of exactly how you want this typeset it is difficult to know for sure, but perhaps one of these is what you are looking for:

or perhaps:

\documentclass{book}
\usepackage{amsmath}
\newcommand{\fib}{\mathrm{fib}}

\begin{document}
\begin{align*}
    &\text{if }  x < 2 & \fib X &= 1 \\
    &\text{otherwise } & \fib X &= (\fib (X - 1)) + (\fib (X - 2))
\end{align*}
Another option is:
\begin{align*}
\fib X = \begin{cases}
    \text{if }  x < 2 & = 1 \\
    \text{otherwise } & = (\fib (X - 1)) + (\fib (X - 2))
\end{cases}
\end{align*}
\end{document}

---

Here is how you can modify the given MWE to obtain better spacing:

Notes:

• @{} is used to eliminate the inter column spacing
• I added {} before the = to get proper math spacing.
• I replaced the $$ ... $$ with \[ ... \]. See Why is \[ ... \] preferable to $$ ... $$? for more details.

• Changes as per egreg's suggestions:

  1. \mathit{foreign}, \mathit{time\_of\_call} and \mathrm{head} for better appearance of the formulas.
  2. Removed \, after \prodtime, and the other uses of \operatorname.

Code:

\documentclass{article}
\usepackage{amsmath}

\newcommand{\prodtime}{\operatorname{prodtime}}

\begin{document}
\[
\begin{array}{l l @{}l}
\prodtime V & X = Y                        &{}= 0 \\
\prodtime V & X = f(\ldots)                &{}= 0 \\
\prodtime V & p(X_1,\,\ldots,\,X_n)        &{}= \prodtime V\,(\operatorname{body} p) \\
\prodtime V & V = \,f(X_1,\,\ldots,\,X_n)  &{}= \prodtime V\,(\operatorname{body} f) \\
\prodtime V & X_0(X_1,\,\ldots,\,X_n)      &{}= \mathit{time\_of\_call} \\
\prodtime V & m(X_1,\,\ldots,\,X_n)        &{}= \mathit{time\_of\_call} \\
\prodtime V & \mathit{foreign}(\ldots)     &{}= 0 \\
\prodtime V & G_\mathrm{head},\,G_\mathrm{tail}
\end{array}
\]
\end{document}

The cases environment of amsmath allows bracing on the left hand side:

\documentclass{article}
\usepackage{amsmath}% http://ctan.org/pkg/amsmath
\newcommand{\fib}{\mathrm{fib}}
\begin{document}
\begin{gather*}
  \fib\,X = \begin{cases}
    1 & \text{if } X<2 \\
    \fib(X-1)+\fib(X-2) & \text{otherwise}
  \end{cases}
\end{gather*}
\end{document}

The contents of cases is much like that of an array. In fact, if you want more control over element placement, the following produces an equivalent output:

\begin{gather*}
  \fib\,X = \left\{\begin{array}{@{}l@{\quad}l}
    1 & \text{if } X<2 \\[\jot]
    \fib(X-1)+\fib(X-2) & \text{otherwise}
  \end{array}\right.
\end{gather*}

Now you can even change the braces, or the alignment.