What binary sequence a₁,a₂,a₃,...a_n,... can be defined by the equation: (a_n)XOR (3*a_n)=a_n+1?
Provide the proof of your formula.

Consider an = 2^(n-1)

a1, a2, a3. a4, …  = 1, 10, 100, 100, ,,,

Use induction 

3 a1 = 11

= a1 XOR 3 a1 = 01 XOR 11 = 10 = a2

now consider 

an XOR 3an

= a^(n-1) XOR  (2 an + 1 an )

= 0 2*n + 1 2^(n-1)   XOR  1 2^n + 1 2^(n-1)

(done pair-wise)

=  1 2*n + 0 2^(n-1)

= 2^n = a_(n+1)

QED

i.e.:  01000… XOR  11000… = 10000…  

Edited on October 31, 2018, 9:56 am

Posted by Steven Lord on 2018-10-31 09:55:32