3
$\begingroup$

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 !

$\endgroup$
2
  • $\begingroup$ What if $C = 1$ and $a_k = 1$ for all positive integers $k$? $\endgroup$
    – VTand
    Feb 19, 2022 at 6:52
  • $\begingroup$ @VTand sorry so much! (a_n) is the sequence of numbers such that all numbers are DIFFERENT. Thank you ! $\endgroup$ Feb 19, 2022 at 6:56

1 Answer 1

0
$\begingroup$

You're asking to prove 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 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(nc_j + \sum_{i=1}^{n}b_{j,i}\right) + c_j + b_{j,n+1} \\ & \le (nH_{n}c_j + nb_{j,1}) + c_j + (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$ gives

$$b_{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{eq3A} shows all prime factors of any $a_i$ must divide $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 that $b_{j,i} \le H_kc_j + b_{j,1}$ for all $1 \le i \le k + 1$. Thus, considering all of the $r$ distinct prime factors, we have that all $a_i$ for $1 \le i \le k + 1$ must be distinct positive factors of

$$M = \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 the number-of-divisors function $\sigma_0()$, the harmonic number upper bound of $H_k \le \ln(k) + 1$ 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) \\ & = \prod_{j=1}^{r}(\lfloor H_{k}c_{j} \rfloor + b_{j,1} + 1) \\ & \le \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}$$

With $k = e^x$, we get $k \to \infty$ means $x \to \infty$. Also, \eqref{eq8A} becomes

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

However, exponential functions grow faster than any polynomial (e.g., as can been seen here 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 hold for large enough $x$ and, thus, large enough $k$.

This contradiction concludes proving that \eqref{eq1A} can't always be true.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .