Given the following function f:
$$f(n,x,y)=\begin{cases}2x+2y&\text{for }n=0\\ 0&\text{for }n>0\text{ and }y>x\\ 1&\text{for }n>0\text{ and }x=y=0\\ f(n-1,0,f(n,x-1,y))&\text{for }n>0,x>0,\text{ and }y=0\\ f(n-1,f(n,x-1,y-1),f(n,x-1,y))&\text{otherwise}\end{cases}$$
I'm trying to use mathematical induction to prove that $f(1, x, y)$ when $x \ge y$ is equivalent to: $$ g(x, y) = {x \choose y} = 2^x \frac{x!}{y! (x-y)!} $$
For the second induction step:
(ii): $f(1, x, y+1)$ = $ 2^x\frac{x!}{(y+1)! (x-y-1)!}$
Instead of $2^x(...)$ I get $2^{(x+1)}(...)$. What am I doing wrong?
Induction step (ii):
$f(1, x, y+1) = f(0, f(1, x-1, y), f(1, x-1, y+1) = 2 ((f(1, x-1, y) + f(1, x-1, y+1)) = 2^{(x+1)}(\frac{(x-1)!(y+1)+(x-1)!(x-y-1)}{(x-y-1)!(y+1)!}) = 2^{(x+1)} \frac{x!}{(y+1)! (x-y-1)!}$
You've simplified it down to $2(f(1,x-1,y)+f(1,x-1,y+1)$. The next step is wrong. It's much easier to see this when we write it in terms of binomials, because then we have
$$2(f(1,x-1,y)+f(1,x-1,y+1)=2\cdot 2^{x-1}\left(\binom{x-1}{y}+\binom{x-1}{y+1}\right)=2^x\binom{x}{y}$$
where the last step is due to Pascal's identity.