Prove that a recurrence for Rule 30 is: B2=MOD(A1+B1+(1+B1)*C1,2)

Question

Prove that Rule 30 satisfies the recurrence:

$$T(1, k) = [k = N]$$ $$T(n,k)=(T(n-1,k-1)+T(n-1,k)+(T(n-1,k)+1) T(n-1,+1+k)) \bmod 2$$ where [ ] is the Iverson bracket.

(*start*)
(*Mathematica*)
Clear[t, n, k, x];
nn = 180;
t[1, k_] := t[1, k] = If[k == nn, 1, 0];
t[n_, k_] := 
  t[n, k] = 
   Mod[t[-1 + n, -1 + k] + 
     t[-1 + n, 0 + k] + (1 + t[-1 + n, 0 + k]) t[-1 + n, +1 + k], 2];
ArrayPlot[Table[Table[t[n, k], {k, 1, 2*nn}], {n, 1, nn}]]
(*end*)

---

In Excel the spreadsheet formula in cell B2 is slighly shorter: =MOD(A1+B1+(1+B1)*C1,2)

---

I recorded the partial proof in the OEIS at the page for Rule 30 A070950, and it will probably be published when the editors have the time to look at it.

Answer 1

This was my starting point: B2=(IF(AND(A1=1,B1=1,C1=1),0,1)*IF(AND(A1=1,B1=1,C1=0),0,1)*IF(AND(A1=1,B1=0,C1=1),0,1)*IF(AND(A1=0,B1=0,C1=0),0,1)) + (IF(AND(A1=1,B1=0,C1=0),1,0) * IF(AND(A1=0,B1=1,C1=1),1,0)* IF(AND(A1=0,B1=1,C1=0),1,0)* IF(AND(A1=0,B1=0,C1=1),1,0))

Which I simplified into:

From Mats Granvik, Dec 06 2019: (Start)

The following recurrence expresses the rules in rule 30, except that instead of If, Or, And, Not, we use addition, subtraction, and multiplication.

T(n, 1) = 0
T(n, 2) = 0
T(1, 3) = 1

T(n, k) = [2*n + 1 >= k] ((1 - (T(n - 1, k - 2)*T(n - 1, k - 1)T(n - 1, k)))(1 - T(n - 1, k - 2)T(n - 1, k - 1)(1 - T(n - 1, k)))(1 - (T(n - 1, k - 2)(1 - T(n - 1, k - 1))T(n - 1, k)))(1 - ((1 - T(n - 1, k - 2))(1 - T(n - 1, k - 1))(1 - T(n - 1, k))))) + ((T(n - 1, k - 2)(1 - T(n - 1, k - 1))(1 - T(n - 1, k)))*((1 - T(n - 1, k - 2))*T(n - 1, k - 1)T(n - 1, k))((1 - T(n - 1, k - 2))T(n - 1, k - 1)(1 - T(n - 1, k)))((1 - T(n - 1, k - 2))(1 - T(n - 1, k - 1))*T(n - 1, k))).

Discarding the term after the plus sign, multiplying/expanding the terms out and replacing all exponents with ones, gives us this simplified recurrence:

T(n, 1) = 0
T(n, 2) = 0
T(1, 3) = 1
T(n, k) = T(-1 + n, -2 + k) + T(-1 + n, -1 + k) - 2 T(-1 + n, -2 + k) T(-1 + n, -1 + k) + (-1 + 2 T(-1 + n, -2 + k)) (-1 + T(-1 + n, -1 + k)) T(-1 + n, k).

That in turn simplifies to:

T(n, 1) = 0
T(n, 2) = 0
T(1, 3) = 1
T(n, k) = Mod(T(-1 + n, -2 + k) + T(-1 + n, -1 + k) + (1 + T(-1 + n, -1 + k)) T(-1 + n, k), 2).

(End)