Question: Consider following function
$f: \mathbb{N}\times\mathbb{N} \rightarrow \mathbb{N}$:
\begin{align\*}
 f(x ,y) = 
 \begin{cases}
 0 & \text{if } x < y\\
 2^x & \text{if } y = 0\\
 2 \cdot (f(x - 1, y - 1) + f(x - 1, y)) & \text{else.}\\
 \end{cases}
\end{align\*}

I want to prove that $f(x, y) = 2^x \cdot {x \choose y}$, $x, y \in \mathbb{N}$, $x \geq y$.

I do see that $f(x - 1, y - 1)$ resembles ${x - 1 \choose y - 1}$ and $f(x - 1, y)$ resembles ${x - 1 \choose y}$, $\left({x \choose y} = {x - 1 \choose y - 1} + {x - 1 \choose y}\right)$ but I don't know where to go from this.

Answer: 
Hint: If $g(x,y)=\frac{1}{2^x}f(x,y)$ then show that you get: $$g(x,y)=\begin{cases}0&x<y\\1&y=0\\g(x-1,y-1)+g(x-1,y)&\text{else}\end{cases}$$

After that show that $g(x,y)=\binom x y.$
Going directly, I would try induction on $x$. 

If $x=0$, $$f(0,y) = \begin{cases} 1 & y = 0 \\ 0 & \text{otherwise}\end{cases}$$
as required.

Now fix $x$, and let $F(y) = f(x,y)$. You have $F(0) = 2^{x}$, and (by assumption), $$F(y) = 2\left(2^{x-1}\binom{x-1}{y-1} + 2^{x-1}\binom{x-1}{y}\right) = 2^{x}\binom{x}{y}$$
which works up until $F(x) = 2^x$, and then the rest are $0$.