Consider the recurrence relation a_1 = 1, a_{2n} = 2*a_n - 1, and a_{2n+1} = 2*a_n + 1, for n = 1.

The value of a_{100...

Question

Consider the recurrence relation a_1 = 1, a_{2n} = 2*a_n - 1, and a_{2n+1} = 2*a_n + 1, for n >= 1.

The value of a_{100} is __________.

Accepted Answer

a_{100} = 73. This recurrence builds a_n from a_{n/2} (or a_{(n-1)/2} for odd indices). To evaluate a_100, we repeatedly halve the index and apply the rule. The pattern is closely related to the binary representation of n: each 0-bit contributes a factor of -1 and each 1-bit a factor of +1 in a signed binary expansion. Starting from a_1=1, we unwind the recursion along the path from 100 down to 1.