# figuring out an integer function

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

• oeis.org/… So there are two sequences :). Sep 20, 2015 at 10:33
• @Hetebrij: Thank you for sharing this link :). BTW Actually a polynomial of 10th degree can also generate these numbers :D. Sep 20, 2015 at 10:34
• Polynomial also look nice: $$\frac{123 n^8}{4480}-\frac{437 n^7}{480}+\frac{4161 n^6}{320}-\frac{6187 n^5}{60}+\frac{945023 n^4}{1920}-\frac{688343 n^3}{480}+\frac{8278267 n^2}{3360}-\frac{89957 n}{40}+819$$ producing $$\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) & = & 45481 \\ f(11) & = & 144413 \\ f(12) & = & 408651 \\ f(13) & = & 1041053 \\ f(14) & = & 2422525 \\ f(15) & = & 5220477 \end{array}$$ Sep 20, 2015 at 10:55
• @NikolayGromov: the polynomial looks nicer written as $$\binom{n}{1}+3\binom{n}{3}+4\binom{n}{4} +15\binom{n}{5}+36\binom{n}{6}+105\binom{n}{7}+288\binom{n}{8}+819\binom{n}{9}$$ actually, this is a different polynomial
– robjohn
Sep 20, 2015 at 11:07
• that's 9th order polynomial Sep 20, 2015 at 11:13

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

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

• @NikolayGromov: really? I hadn't tried simplifying the fairly complicated expression involving $(2n-3)!!$ to see if they were the central binomial coefficients. Why make it look more complicated?
– robjohn
Sep 20, 2015 at 10:50
• It is just more explicit. Otherwise no difference. Sep 20, 2015 at 10:53
$$\frac{2^{n-1} (2 n-3)\text{!!}}{(n-1)!}$$
$$\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}$$