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. 
 A: 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.$
A: 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$. 
A: 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.
