<s>[INST] Proving recursive function outputs $2^x \cdot {x \choose y}$ 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. 
 [/INST] 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$. 
</s>