AustriaMO2013

Question

We order the positive integers in two rows in the following manner: 1 3 6 11 19 32 53 ... 2 4 5 7 8 9 10 12 13 14 15 16 17 18 20 to 31 33 to 52 54 ... We first write 1 in the first row, 2 in the second and 3 in the first. After this, the following integers are written in such a way that an individual integer is always added in the first row and blocks of consecutive integers are added in the second row, with the leading number of a block giving the number of (consecutive) integers to be written in the next block. We name the numbers in the first row a_1, a_2, a_3, Determine an explicit formula for a_n. G. Baron, Vienna

Accepted Answer

We first note that a_1 = 1, a_2 = 3 and a_3 = 6 hold. It is quite straight-forward to note that a block of length a_n-1 + 1 starts with the number a_n + 1, and that this block therefore ends on the number a_n + (a_n-1 + 1), which yields a_n+1 = a_n + a_n-1 + 2. This recursion has the constant solution a_n -2, and the homogeneous recursion a_n+1 = a_n + a_n-1 is obviously of Fibonacci type. Writing the Fibonacci sequence in the form F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2 and so on, we can easily check that a_n = F_n+3 - 2 holds for n = 1, 2, 3, and this therefore yields an explicit formula for a_n.