Problem 3

A sequence of real numbers

a_0,a_1,\ldots

is said to be good if: (i)

a_0

is a positive integer; (ii) for each non-negative integer

i

a_{i+1}=2a_i+1

a_{i+1}=\frac{a_i}{a_i+2}

; (iii) there exists a positive integer

k

such that

a_k=2014

. Find the smallest positive integer

n

such that there exists a good sequence with

a_n=2014

Step 1 of 4: Linearize the two moves

Previous step Next step

\frac1{a_{i+1}+1}=\frac1{2(a_i+1)}\quad\text{or}\quad\frac1{a_{i+1}+1}=\frac12\left(\frac1{a_i+1}+1\right)

Detailed analysis

This reciprocal identity is obtained directly from the two allowed transitions. Iterating it expresses the reciprocal of the target plus one as a binary affine combination of the initial reciprocal plus one.