<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] short answer:  Do induction on the values of $n = x -y$ starting with $n = 0$.
Prove the Base case and the induction step by induction on $y$ starting with $y=0$.
That is the Base case is to prove that the result is true for $x-y=0$ and showing this holds for $f(y,y)$ by doing base case $f(0,0)$ and doint induction on $y$ shoowing true for $f(y,y) \implies $ true for $f(y+1, y+1)$.
Then to the Induction step by assume true for all $x-y=n$ and showing by induction it holds for $f(y+ (n+1),y)$ doing a base case on $f(n+1,0)$ then show true for $f(y+n+1,y) \implies $true for$f((y+1) + (n+1),y+1)$.
Induction within induction.  
To wit:
========
Claim 1:  For all $n \ge 0$ and all $x = y+n$ then $f(x,y) = 2^x{x\choose y}$.
Well, prove this with  induction.
Base case of Claim 1: $n= 0$.
Pf:  We'll prove the base case by  induction.
Claim: For all $x = y$, $f(x,y) = 2^x{x \choose y}$
Base case: $x = 0$ then $f(0,0) = 2^0 =1$ and ${0\choose 0} =1$.
Induction step:  Assume true for $x$ that $f(x,x) = 2^x{x\choose x}$.
Then $f(x+1,x+1) = 2f(x,x) + f(x,x +1) = 2\cdot 2^x{x\choose x} + 0=2^{x+1}{x\choose x}$.  But ${x\choose x}= 1={x+1\choose x+1}$
Thus Base case of Claim 1:
Induction step:
Assume it is true that for all $x-y=n$ our result is true:
Claim 2:  For all $x = y+ (n+1)$ then $f(x,y) = 2^x{x\choose y}$
We will prove Claim 2 by induction:
Base case of Claim 2:  $f(n+1,0) = 2^{n+1}$ and ${n+1\choose 0} =1$.
Induction step of Claim 2: Suppose it is true for $x = y+(n+1)$.
Then $f(x+1, y+1) = 2(f(x,y) + f(x, y+1))$.
$f(x,y) = 2^x{x \choose y}$.  But notice $x-(y+1) = n$ and we know it is true for all $x' = y'+n$ so it is true for so $f(x,y+1) = 2^x{x\choose y+1}$.
So $f(x+1,y+1) = 2(2^x{x \choose y} + 2^x{x\choose y+1})=$
$2^{x+1} ({x \choose y} + {x\choose y+1})=$
$2^{x+1} (\frac {x!}{(x-y)!y!} + \frac {x!}{(x-y-1)!(y+1)!})=$
$2^{x+1}(\frac {x!(y+1) + x!(x-y)}{(x-y)!(y+1)!})=$
$2^{x+1}(\frac {x!(x+1)}{((x+1)-(y+1))!(y+1)!})=$
$2^{x+1}(\frac {(x+1)!}{((x+1)-(y+1))!(y+1)!})= 2^{x+1}{x+1\choose y+1}$.
So it is true for all $x= y+(n+1)$.
That proves our induction step of Claim 2.
So Claim 2 is proven.
Proving Claim 2 proves the induction step of Claim 1.
So Claim 1 is proven.
</s>