1

I need help understanding what I am doing wrong.

I need to prove (by induction): $ f(n) = \begin{cases} 1 & \text{if $n=1$} \\ (2*n - 1)*f(n - 1) & \text{if $n>=2$} \end{cases} $

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

I start with basis for $n=1$ and $2$:

$f(1) = \frac{2!}{(2*1!)}$ -> 1=1 OK!

$f(2) = (2*2)!/(2!*2^2) \to 3=3 $ OK!

Then we assume $n = k$ then $f(k) = \frac{(2*k)!}{(k!*2^{k})}$

We need to show that it holds for $k+1$:

$(2*k + 1)*f(k) = (2*k + 1)*\frac{(2*k)!}{(k!*2^{k})}$

$(2*k + 1)*\frac{(2*k)!}{(k!*2^{k})}$

$(2*k + 1)*(2*k)!*\frac{1}{(k!*2^{k}*(2*k + 1))}$

Here is my issue. I end up with the same equation for $k$, and not $k+1$:

$\frac{(2*k)!}{(k!*2^{k})}$

What am I doing wrong?

Any help will be greatly appreciated!

Bumblebee
  • 1,209
Leaf313
  • 13

2 Answers2

0

You have\begin{align}f(k+1)&=(2k+1)f(k)\\&=(2k+1)\frac{(2k)!}{k!2^k}\\&=\frac{(2k+2)(2k+1)}{2(k+1)}\frac{(2k)!}{k!2^k}\\&=\frac{(2k+2)!}{(k+1)!2^{k+1}}.\end{align}

José Carlos Santos
  • 427,504
0

Your writing is a bit unclear, but if you assume:

$$f(k)=\frac{(2k)!}{k!\cdot 2^k}$$

just calculating $f(k+1)=(2k+1)f(k)=(2k+1)\frac{(2k)!}{k!\cdot 2^k}=\frac{(2k+1)!}{k!\cdot 2^k}$ does not fully solve the problem, as you've noticed. You need to additionally extend the fraction by $2k+2=2(k+1)$:

$$\ldots=\frac{(2k+1)!}{k!\cdot 2^k}=\frac{(2k+1)!}{k!\cdot 2^k}\frac{2k+2}{2(k+1)}=\frac{(2(k+1))!}{(k+1)!\cdot 2^{k+1}}$$

  • Thanks, for the reply. I am just wondering how would one see that you need to extend the fraction? – Leaf313 Nov 12 '21 at 09:45
  • You know you want to get something like $\frac{(2k+2)!}{(k+1)!\cdot 2^{k+1}}$. You got almost that, but with $(2k+1)!$ in the numerator. Thus, it is really tempting to multiply both the numerator and the denominator by $2k+2$ - that makes the numerator "just right", and then you realise that it also makes the denominator "just right". –  Nov 12 '21 at 13:58