Let $\{a_n\}_{n\geq 0}$ be an arithmetic sequence with difference $d$ and $1\leq a_0\leq d$. Denote the sequence as $S_0$, and define $S_n$ recursively by two operations below: Step $1$: Denote the first number of $S_n$ as $b_n$, and remove $b_n$. Step $2$: Add $1$ to the first $b_n$ numbers to get $S_{n+1}$. Prove that there exists a constant $c$ such that $b_n=[ca_n]$ for all $n\geq 0$, where $[]$ is the floor function.
Problem
Source: 2017 Taiwan TST Round 3
Tags: arithmetic sequence, algebra, floor function, function
12.05.2020 09:40
$a_1$ is the first number or second number of $S_0$?
03.04.2021 00:10
Solved together with MathPassionForever, p_square, Rg230403, Pluto1708, Arwen713 Let $c$ be the positive root of $d x^2-d x-1=0$. Define $T_n = \{k \mid b_k+k \ge n , 0\le k< n \}$ Note that for a given $k$ , such that $0\le k<n$ deleting $b_k$ increments $a_n$ by $1$ if and only if $b_k+k \ge n$. Hence we have that $$b_n = a_n + |T_n|$$Now we prove by induction that $b_n = \lfloor ca_n \rfloor$ Base Case - $n = 0$ As $c$ is root of $d x^2-d x-1=0$ , $c>1$ and $c(c-1)=\frac{1}{d} $ $c-1 < c(c-1) = \frac 1 d \le \frac {1} {a_0} \implies ca_0-a_0 < 1$ Hence $a_0 < ca_0 < a_0 + 1$ and $\lfloor ca_0 \rfloor = a_0 = b_0$ Assumption - Assume $b_t = \lfloor ca_t \rfloor$ for all $t<n$ Inductive Step - We have $$b_n = a_n + |T_n|$$$$ = a_n + |\{k \mid b_k+k \ge n , 0\le k< n \}|$$$$= a_n + |\{k \mid \lfloor ca_k \rfloor+k \ge n , 0\le k< n \}| $$$$= a_n + |\{k \mid ca_k+k \ge n , 0\le k< n \}| $$$$= a_n + |\{k \mid c(a_0+k d)+k \ge n , 0\le k< n \}| $$$$= a_n + |\{k \mid k \ge \frac{n-ca_0}{d c+1} , 0\le k< n \}| $$$$= a_n + |\{k \mid n> k \ge \frac{n-ca_0}{d c+1} \}| $$$$ = a_0 + n d + n- \lceil \dfrac{n-ca_0}{d c+1} \rceil $$Hence $$a_0 + n d + n- \dfrac{n-ca_0}{d c+1}-1 < b_n \le a_0 + n d + n- \dfrac{n-ca_0}{d c+1} $$Now we claim that $$a_0 + n d + n- \dfrac{n-ca_0}{d c+1} = ca_n = c a_0 + c n d$$$$\iff a_0 d c + a_0 + n d^2 c + nd +n d c + c a_0 = a_0 c^2 d + a_0 c + nc^2 d^2 + c n d $$$$\iff a_0 d c + a_0 + n d^2 c + nd = a_0 c^2 d + nc^2 d^2 $$$$\iff (a_0+n d)(1+dc - d c^2) = 0$$Which is true !! Hence $$ ca_n -1 < b_n \le ca_n$$$$\implies b_n =\lfloor ca_n \rfloor $$QED.
03.04.2021 10:27