Prove that there is no positive integer $C$ and the sequence of positive integers$ (a_n) $ satisfies : ${a_{k+1}}^k|C^k(a_1.a_2...a_k)$ for all $k$

Question

Prove that there is no positive integer $C$ and the sequence of positive integers$ (a_n) $ satisfies : ${a_{k+1}}^k|C^k(a_1.a_2...a_k)$ for all $k\in Z+$ ($(a_n)$ is the sequence of numbers such that all numbers are DIFFERENT.)

Suppose there exists a positive integer $C$ and such a sequence $(a_n)$ .

Consider any prime $p$. Set $vp(C) = C' , vp(a_i)=b_i$

From the assumption $\Rightarrow kb_{k+1} \le kC'+b_1+b_2+...+b_k$

Consider the sequence $(v_n)$ as follows: $v_1=b_1 ; kv_{k+1} = kC'+v_1+v_2+...+v_k$ Thus, $b_k \le v_k$

$kv_{k+1}=kC'+v_1+v_2+...+v_k=C'+(k-1)C'+v_1+v_2+...+v_{k-1}+v_k = C'+ (k-1)v_k+v_k=C'+kv_k$ $\Rightarrow v_{k+1} = C'/k + v_k$

So if $k→+°$ , then because $b_k \in Z+$ $(b_n)$ is bounded on .

So $(b_n)$ is bounded above and below .

There should be an infinite $i$ such that there exists an infinite $j$ such that $b_i = b_j$

This is all I can do , this is a very difficult problem for me . Hope to get help from everyone. Thanks very much !

• VTand: What if $C = 1$ and $a_k = 1$ for all positive integers $k$?
• yoursmileeeeee: @VTand sorry so much! (a_n) is the sequence of numbers such that all numbers are DIFFERENT. Thank you !

Answer 1

You're asking about proving there's no positive integer $C$ and an infinite set of distinct positive integers $a_i$ such that

$$(a_{k+1})^k \mid C^k\left(\prod_{i=1}^{k}a_i\right) \tag{1}\label{eq1A}$$

is true for all positive integers $k$. Assume there is some such a positive integer $C$ and set of $a_i$. For any prime $p_j$ which divides $C$ or one of the $a_i$, using the $p$-adic order function, let

$$b_{j,i} = \nu_{p_{j}}(a_i), \; \; c_j = \nu_{p_{j}}(C) \tag{2}\label{eq2A}$$

We'll prove using induction, with the harmonic numbers (i.e., $H_1 = 1$ and $H_{n+1} = H_n + \frac{1}{n+1} \; \forall \; n \ge 1$), for all $k \ge 1$ that

$$kb_{j,k+1} \le kc_j + \sum_{i=1}^{k}b_{j,i} \le kH_{k}c_j + kb_{j,1} \; \; \to \; \; b_{j,k+1} \le H_{k}c_j + b_{j,1} \tag{3}\label{eq3A}$$

For $k = 1$, we get from \eqref{eq1A} and \eqref{eq2A} that

$$b_{j,2} \le c_{j} + b_{j,1} = H_{1}c_{j} + b_{j,1} \tag{4}\label{eq4A}$$

so \eqref{eq3A} works in the base case since $H_1 = 1$. Assume \eqref{eq3A} is true for $k = n$ for some $n \ge 1$. Then, for $k = n + 1$, \eqref{eq1A}, \eqref{eq2A} and \eqref{eq3A} give that

$$\begin{equation}\begin{aligned} (n+1)b_{j,n+2} & \le (n + 1)c_j + \sum_{i=1}^{n+1}b_{j,i} \\ & = \left({\color{blue}{nc_j + \sum_{i=1}^{n}b_{j,i}}}\right) + c_j + {\color{green}{b_{j,n+1}}} \\ & \le ({\color{blue}{nH_{n}c_j + nb_{j,1}}}) + c_j + ({\color{green}{H_{n}c_j + b_{j,1}}}) \\ & = ((n+1)H_{n} + 1)c_j + (n + 1)b_{j,1} \\ & = (n + 1)\left(H_{n} + \frac{1}{n+1}\right)c_j + (n + 1)b_{j,1} \end{aligned}\end{equation}\tag{5}\label{eq5A}$$

Dividing both sides of \eqref{eq5A} by $n + 1$ and using $H_{n+1} = H_{n} + \frac{1}{n+1}$ gives

$$b_{j,n+2} \le \left(H_{n} + \frac{1}{n+1}\right)c_j + b_{j,1} = H_{n+1}c_j + b_{j,1} \tag{6}\label{eq6A}$$

so \eqref{eq3A} holds for $k = n + 1$ as well. Thus, by induction, \eqref{eq3A} holds for all positive integers $k$.

Note \eqref{eq1A} shows each prime factor $p_j$ of any $a_{k+1}$ must have $p_j \mid C$ and/or $p_j \mid a_i$ for some $i \le k$. If $p_j \not\mid C$, so $p_j \mid a_i$ $i \gt 1$, then using \eqref{eq1A} again shows that $p_j \mid a_q$ for some $q \lt i$. This can continue until we get $p_j \mid a_1$. Thus, we have that all prime factors of any $a_{k+1}$ divides $Ca_1$, so there are only a finite number of them, say some $r \ge 1$. Also, the harmonic numbers being a strictly increasing sequence means, from \eqref{eq3A}, that $b_{j,i} \le H_{k}c_j + b_{j,1}$ for all 1ドル \le i \le k + 1$. Thus, considering all of the $r$ prime factors being used, we have that all $a_i$ for 1ドル \le i \le k + 1$ must be factors of

$$M_k = \prod_{j=1}^{r}p_j^{e_j}, \; e_j = \lfloor H_{k}c_{j} \rfloor + b_{j,1} \tag{7}\label{eq7A}$$

Thus, using that the $a_i$ for 1ドル \le i \le k + 1$ comprise $k + 1$ distinct positive factors of $M_k$, the number-of-divisors function $\sigma_0()$, an upper bound for the harmonic numbers growth rate of $H_k \lt \ln k + 1$ (for $k \ge 2$, from $H_k = \ln k + \gamma + \frac{1}{2k} - \varepsilon_k$ with $\gamma \approx 0.5772$ and $\varepsilon_k \ge 0$) and $c_{m} = \max(c_{1} + 1, \ldots, c_{r} + 1)$, we get for large enough $k$ (i.e., where $\ln k \gt \max(c_{1} + b_{1,1} + 1, \ldots, c_{r} + b_{r,1} + 1)$) that

$$\begin{equation}\begin{aligned} k + 1 & \le \sigma_0(M_k) \\ & = \prod_{j=1}^{r}(\lfloor H_{k}c_{j} \rfloor + b_{j,1} + 1) \\ & \lt \prod_{j=1}^{r}(c_{j}\ln{k} + c_{j} + b_{j,1} + 1) \\ & \lt \prod_{j=1}^{r}((c_{j} + 1)\ln{k}) \\ & \le \prod_{j=1}^{r}(c_{m}\ln{k}) \\ & = c_{m}^{r}(\ln{k})^{r} \end{aligned}\end{equation}\tag{8}\label{eq8A}$$

For some real $x$ with $k = e^x$, we have that $k \to \infty$ means $x \to \infty$. Also, \eqref{eq8A} becomes

$$e^x + 1 \lt c_{m}^{r}x^{r} \tag{9}\label{eq9A}$$

However, exponential functions grow faster than any polynomial (e.g., as can been seen for our case by using L'Hôpital's rule $r$ times to get $\lim_{x \to \infty}\frac{e^x + 1}{c_{m}^{r}x^{r}} = \lim_{x \to \infty}\frac{e^x}{c_{m}^{r}(r!)} = \infty$, or by using a post like Proving exponential is growing faster than polynomial), so \eqref{eq9A} can't be true for large enough $x$ and, thus, large enough $k$.

This contradicts the assumption that such a $C$ and set of $a_i$ exists, proving that \eqref{eq1A} can't always be true.