2019 CIME I Problems/Problem 15

Let $(\mathcal{F}_n)_{n \geq 1}$ be a sequence of functions going from $\mathbb{N}^+$ to $\mathbb{N}^+$ defined recursively by $\mathcal{F}_1(n)=1$ and $\mathcal{F}_k(n)=\sum_{d|n}\mathcal{F}_{k-1}(d)$ for all $k \geq 1$ . Compute the greatest integer less than or equal to $\frac{\mathcal{F}_{2019}(864)}{\mathcal{F}_{2019}(648)}$ .

Solution

Note that the function on the right is $F_{k}(n)$ ’s sum function, so if $F_{k}(n)$ is multiplicative so is $F_{k+1}(n)$ . Now since $F_{1}(n)=1$ is multiplicative, it is not hard to see using induction that all $F_{k}(n)$ are multiplicative too.

Therefore we can just consider one prime and its exponent. Say $n=p_1^{e_1}\cdots p_k^{e_k}$ . Note that $F_{1}(p^e)=1$ and $F_2(p^e)=1+1+1+\cdots +1=e+1=\binom{e+1}{1}$ . Then $F_3(p^e)=\sum_{i=0}^e \binom{i+1}{1} =\binom{e+2}{2}$ by the Hockey Stick Identity. We can continue this process (summing and using the hockey stick identity for each exponent) to obtain $F_{2019}(p^e)=\binom{e+2018}{2018}$ .

Now $864=2^5 3^3$ and $648=2^3 3^4$ thus our answer is $\frac{\binom{2023}{2018}\binom{2021}{2018}}{\binom{2021}{2018}\binom{2022}{2018}}=\dfrac{2023 \cdot 2022 \cdot 2021 \cdot 2020 \cdot 2019 \cdot 24}{2022 \cdot 2021 \cdot 2020 \cdot 2019 \cdot 120} = 2023 \cdot \frac{24}{120} = \frac{2023}{5} = 404.6 \rightarrow \boxed{404}$ .

2019 CIME I (Problems • Answer Key • Resources)
Preceded by Problem 14	Followed by Last problem
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All CIME Problems and Solutions

Page

Toolbox

Search

2019 CIME I Problems/Problem 15

Solution

See also