{an}n≥0 is an infinite integer sequence with common difference d, where the first term satisfies 1≤a0≤d. Denote this sequence by S0; we define a sequence of new sequences recursively: the sequence Sn+1 is obtained from Sn by the following two steps.
Step 1. Denote the first term of Sn by bn. 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 bn terms of the sequence.
Prove that there exists a constant c such that bn=[can] holds for all n≥0. Here [⋅] denotes the floor function.
Solution
Below we prove by induction that c=21+1+d4, which is the positive root of the equation c2−c−1/d=0.
First we prove that the statement holds for n=0. By definition b0=a0, and [ca0]=[21+1+4/da0]=a0+[2−1+1+4/da0]=a0+[1+1+4/d2⋅da0]=a0, so b0=[ca0] holds.
Next we prove by induction that the statement holds for all n>0. By the problem statement, the value of bn is obtained from an by adding 1 some number of times: when performing the operation Sk→Sk+1, if that term is increased by 1, then necessarily bk+k≥n and 0≤k<n. For every n, we write the set of such k as Xn={k∣bk+k≥n and 0≤k<n}, and then we have bn=an+∣Xn∣. The key lies in how to compute the size of the set Xn: by induction, we have Xn={k∣[cak]+k≥n and 0≤k<n}={k∣cak+k≥n and 0≤k<n}={k∣ca0+k(1+cd)≥n and 0≤k<n}={k∣1+cdn−ca0≤k<n} Note: here it does not matter even if n<ca0, because 1+cdn−ca0>−1 holds always, and this does not affect the count of k.
Therefore bn=an+∣Xn∣=an+[1+cdcan]=[(1+1+cdc)⋅an]=[can], 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.