figuring out an integer function

Question

$f(1) = 1\\ f(2) = 2\\ f(3) = 6\\ f(4) = 20\\ f(5) = 70\\ f(6) = 252\\ f(7) = 924\\ f(8) = 3432\\ f(9) = 12870$

Then what is $f(n)$ (where $n > 0$)?

I though about many many possibilities but still cannot figure out the expression.

Answer 1

You could approach this kind of question in this way. You'd like to find what is the relation between $f_n$ and $f_{n+1}$ (you believe that there is some) so that's why most of the time it's a good idea to analyze expressions like $\frac{f_{n+1}}{f_n}$ or $f_{n+1}-f_n$. Let's look at $\frac{f_{n+1}}{f_n}$. You may notice that $\frac{f_{n+1}}{f_{n}}\sim 4$ as the sequence grows, more precisely: $$ \begin{array}{ccl} \frac{f_2}{f_1}& = & 2 \\ \frac{f_3}{f_2} & = & 3 \\ \frac{f_4}{f_3} & = &3.(3) \\ \frac{f_5}{f_4} & = & 3.5 \\ \frac{f_6}{f_5} & = & 3.6 \\ \frac{f_7}{f_6} & = & 3.(6)\\ \frac{f_8}{f_7} & = & 3.(714285) \\ \frac{f_9}{f_8} & = & 3.75 \\ \end{array} $$

So you might expect that $\frac{f_{n+1}}{f_{n}} = 4 - g_n$ where $g_n \to 0$ as $n\to +\infty$. Upon more precise calculation we get: $$ \begin{array}{ccl} \frac{f_2}{f_1}& = & 4-\frac{2}{1} \\ \frac{f_3}{f_2} & = & 4-\frac{2}{2} \\ \frac{f_4}{f_3} & = &4-\frac{2}{3} \\ \frac{f_5}{f_4} & = &4-\frac{2}{4} \\ \frac{f_6}{f_5} & = &4-\frac{2}{5} \\ \frac{f_7}{f_6} & = & 4-\frac{2}{6}\\ \frac{f_8}{f_7} & = & 4-\frac{2}{7} \\ \frac{f_9}{f_8} & = & 4-\frac{2}{8} \\ \end{array} $$ So we could see that $\frac{f_{n+1}}{f_n} = 4-\frac{2}{n} = \frac{2(2n-1)}{n}$. From here $$\frac{f_{n+1}}{1} =\frac{f_{n+1}}{ f_n } \times \frac{f_{n}}{f_{n-1}} \times \dots \times \frac{f_2}{f_1} = \frac{2(2n-1)}{n}\times \frac{2(2n-3)}{n-1} \dots = \frac{2^n(2n-1)!!}{n!}$$

which is $\binom{2n}{n}$ as already mentioned

Answer 2

What about this?

$$\frac{2^{n-1} (2 n-3)\text{!!}}{(n-1)!}$$

which gives

$$ \begin{array}{ccl} f(1) & = & 1 \\ f(2) & = & 2 \\ f(3) & = & 6 \\ f(4) & = & 20 \\ f(5) & = & 70 \\ f(6) & = & 252 \\ f(7) & = & 924 \\ f(8) & = & 3432 \\ f(9) & = & 12870 \\ f(10) & = & 48620 \\ f(11) & = & 184756 \\ f(12) & = & 705432 \\ f(13) & = & 2704156 \\ f(14) & = & 10400600 \\ f(15) & = & 40116600 \\ f(16) & = & 155117520 \\ f(17) & = & 601080390 \\ f(18) & = & 2333606220 \\ f(19) & = & 9075135300 \\ f(20) & = & 35345263800 \\ \end{array} $$

Answer 3

The Central Binomial Coefficients $$ \binom{2n-2}{n-1} $$ seem to fit.

Edit: As Nikolay Gromov comments, this is the same sequence as given in his answer, though it is not immediately apparent. This is because $$ (2n-3)!!=\frac{(2n-2)!}{2^{n-1}(n-1)!} $$ so that $$ \frac{2^{n-1}(2n-3)!!}{(n-1)!}=\frac{(2n-2)!}{(n-1)!(n-1)!}=\binom{2n-2}{n-1} $$