Maths Olympiad Prep

Library / /354 of 397

Algebra Difficulty 7.0 National Olympiad Prove it Taiwan

{an}n0\{a_n\}_{n \ge 0} is an infinite integer sequence with common difference dd, where the first term satisfies 1a0d1 \le a_0 \le d. Denote this sequence by S0S_0; we define a sequence of new sequences recursively: the sequence Sn+1S_{n+1} is obtained from SnS_n by the following two steps.

Step 1. Denote the first term of SnS_n by bnb_n. Remove the first term, and shift every remaining term of the sequence forward by one position.

Step 2. Starting from the new first term, add 1 to the first bnb_n terms of the sequence.

Prove that there exists a constant cc such that bn=[can]b_n = [ca_n] holds for all n0n \ge 0. Here [][\cdot] denotes the floor function.

Solution

Below we prove by induction that
c=1+1+4d2, c = \frac{1 + \sqrt{1 + \frac{4}{d}}}{2},
which is the positive root of the equation c2c1/d=0c^2 - c - 1/d = 0.

First we prove that the statement holds for n=0n = 0. By definition b0=a0b_0 = a_0, and
[ca0]=[1+1+4/d2a0]=a0+[1+1+4/d2a0]=a0+[21+1+4/da0d]=a0, \begin{aligned} [ca_0] &= \left[ \frac{1 + \sqrt{1 + 4/d}}{2} a_0 \right] = a_0 + \left[ \frac{-1 + \sqrt{1 + 4/d}}{2} a_0 \right] \\ &= a_0 + \left[ \frac{2}{1 + \sqrt{1 + 4/d}} \cdot \frac{a_0}{d} \right] = a_0, \end{aligned}
so b0=[ca0]b_0 = [ca_0] holds.

Next we prove by induction that the statement holds for all n>0n > 0. By the problem statement, the value of bnb_n is obtained from ana_n by adding 1 some number of times: when performing the operation SkSk+1S_k \rightarrow S_{k+1}, if that term is increased by 1, then necessarily bk+knb_k + k \ge n and 0k<n0 \le k < n. For every nn, we write the set of such kk as
Xn={kbk+kn and 0k<n}, X_n = \{k \mid b_k + k \ge n \text{ and } 0 \le k < n\},
and then we have bn=an+Xnb_n = a_n + |X_n|. The key lies in how to compute the size of the set XnX_n: by induction, we have
Xn={k[cak]+kn and 0k<n}={kcak+kn and 0k<n}={kca0+k(1+cd)n and 0k<n}={knca01+cdk<n} \begin{align*} X_n &= \{k \mid [ca_k] + k \ge n \text{ and } 0 \le k < n\} \\ &= \{k \mid ca_k + k \ge n \text{ and } 0 \le k < n\} \\ &= \{k \mid ca_0 + k(1 + cd) \ge n \text{ and } 0 \le k < n\} \\ &= \{k \mid \frac{n - ca_0}{1 + cd} \le k < n\} \end{align*}
Note: here it does not matter even if n<ca0n < ca_0, because
nca01+cd>1 \frac{n - ca_0}{1 + cd} > -1
holds always, and this does not affect the count of kk.

Therefore
bn=an+Xn=an+[can1+cd]=[(1+c1+cd)an]=[can], \begin{align*} b_n &= a_n + |X_n| = a_n + \left[ \frac{ca_n}{1+cd} \right] \\ &= \left[ \left(1 + \frac{c}{1+cd}\right) \cdot a_n \right] = [ca_n], \end{align*}
and the original statement is proved.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.