Proving recursive function outputs $2^x \cdot {x \choose y}$

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 1

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.

Answer 2

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

Answer 3

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