MathDB
n+3 is a power of 2

Source: India TST 2016 Day 3 Problem 1

July 22, 2016
number theoryrecurrence relationpower of 2geometrybir tinga qimmat ekan boru

Problem Statement

Let nn be a natural number. We define sequences ⟨ai⟩\langle a_i\rangle and ⟨bi⟩\langle b_i\rangle of integers as follows. We let a0=1a_0=1 and b0=nb_0=n. For i>0i>0, we let (ai,bi)={(2ai−1+1,bi−1−ai−1−1)if ai−1<bi−1,(ai−1−bi−1−1,2bi−1+1)if ai−1>bi−1,(ai−1,bi−1)if ai−1=bi−1.\left( a_i,b_i\right)=\begin{cases} \left(2a_{i-1}+1,b_{i-1}-a_{i-1}-1\right) & \text{if } a_{i-1}<b_{i-1},\\ \left( a_{i-1}-b_{i-1}-1,2b_{i-1}+1\right) & \text{if } a_{i-1}>b_{i-1},\\ \left(a_{i-1},b_{i-1}\right) & \text{if } a_{i-1}=b_{i-1}.\end{cases} Given that ak=bka_k=b_k for some natural number kk, prove that n+3n+3 is a power of two.
Back to ProblemsView on AoPS