Trouble with proof by induction

81 Views Asked by At

I am trying to prove that the following recursive function

$$f(n)=\begin{cases}1,\ n=0,\ \\ (2n-1)f(n-1),\ n>0,\end{cases}$$

can be expressed as

$$f(n)=\frac{(2n)!}{n!2^{n}}.$$

I know that this should be done by induction. It is easy to see that for $n=0$ the statement holds, i.e., $f(0)=1$. As for the induction step I have assumed that

$$f(n-1)=\frac{(2n-1)!}{(n-1)!2^{n-1}}$$

holds for some $n\in$ $\mathbb{N}$. From the recursive definition I have that $f(n)=(2n-1)f(n-1)$ in which I have tried to arrive at the desired statement but to no avail. I have tried calculating $(2n-1)f(n-1)$ in various ways but nothing seems to get me there. Furthermore, I am not sure whether this even is the right approach.

$\textbf{Side note:}$ In the problem it is not clear as to how $(2n)!$ is defined which also confuses me a bit. I am assuming it is defined as $(2n)!=2n(2n-1)!$ but it could also be $(2n)!=2n(2(n-1))!$ which obviously results in completely different answers.

Any hints would be highly appreciated. Thanks in advance.

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose that$$f(n-1)=\frac{\bigl(2(n-1)\bigr)!}{(n-1)!2^{n-1}}=\frac{(2n-2)!}{(n-1)!2^{n-1}}.$$Then\begin{align}f(n)&=(2n-1)f(n-1)\\&=(2n-1)\frac{(2n-2)!}{(n-1)!2^{n-1}}\\&=\frac{(2n)(2n-1)(2n-2)!}{(2n)(n-1)!2^{n-1}}\\&=\frac{(2n)!}{n\times(n-1)!\times2\times2^{n-1}}\\&=\frac{(2n)!}{n!2^n}.\end{align}