Consider some arbitrary number sequence like the decimal expansion of $\pi$ = {3, 1, 4, 1, 5, 9, 2}. Prepend the sequence with the number $1$ so that you get {1, 3, 1, 4, 1, 5, 9, 2}.
Then plug it into the first column in a matrix that has the following recurrence definition:
$$\begin{align} T(n,1) &= (n-1)\text{th digit of }\pi, \\ T(n,2) &= T(n,1) - T(n-1,2), \\ \text{for } k>2, T(n,k) &= \sum\limits_{i=1}^{k-1} T(n-i,k-1)-\sum\limits_{i=1}^{k-1} T(n-i,k) \end{align} $$
That table looks like this:
$$\displaystyle \left( \begin{array}{cccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 3 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & -2 & 3 & 0 & 0 & 0 & 0 & 0 \\ 4 & 6 & -2 & 3 & 0 & 0 & 0 & 0 \\ 1 & -5 & 3 & -2 & 3 & 0 & 0 & 0 \\ 5 & 10 & 0 & 3 & -2 & 3 & 0 & 0 \\ 9 & -1 & 2 & -3 & 3 & -2 & 3 & 0 \\ 2 & 3 & 7 & 7 & -3 & 3 & -2 & 3 \end{array} \right)$$
Then calculate the matrix inverse of the matrix above:
$$\displaystyle \left( \begin{array}{cccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & \frac{1}{3} & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & \frac{2}{9} & \frac{1}{3} & 0 & 0 & 0 & 0 & 0 \\ 0 & -\frac{14}{27} & \frac{2}{9} & \frac{1}{3} & 0 & 0 & 0 & 0 \\ -1 & -\frac{1}{81} & -\frac{5}{27} & \frac{2}{9} & \frac{1}{3} & 0 & 0 & 0 \\ 1 & -\frac{146}{243} & -\frac{28}{81} & -\frac{5}{27} & \frac{2}{9} & \frac{1}{3} & 0 & 0 \\ -1 & -\frac{688}{729} & -\frac{11}{243} & -\frac{1}{81} & -\frac{5}{27} & \frac{2}{9} & \frac{1}{3} & 0 \\ 0 & \frac{694}{2187} & -\frac{850}{729} & -\frac{92}{243} & -\frac{1}{81} & -\frac{5}{27} & \frac{2}{9} & \frac{1}{3} \end{array} \right)$$
Why then is there the Möbius function sequence in the first column?
I have checked this for random sequences in programs like this:
(*Mathematica*)
Clear[t, n, k, a, b];
nn = 8;
a = Flatten[{1, RealDigits[N[Pi, nn - 1]][[1]]}]
Length[a]
t[n_, 1] := t[n, 1] = a[[n]];
t[n_, k_] :=
t[n, k] =
If[And[n > 1, k > 1],
If[k == 2, t[n, k - 1] - t[n - 1, k],
Sum[t[n - i, k - 1], {i, 1, k - 1}] -
Sum[t[n - i, k], {i, 1, k - 1}]], 0];
A = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A]
MatrixForm[Inverse[A]]
for up to 100 times 100 matrices and I always get the Möbius function in the first column.
I believe it has something do with the fact that the divisibility matrix equal to 1 if k divides n and 0 otherwise:
$$\displaystyle \left( \begin{array}{cccccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \end{array} \right)$$
satisfies the recurrence, that (edit 21.7.2014) Jeffrey Shallit formulated for me:
$$\begin{align} T(n,1) &= 1, \\ \text{for } k>1, T(n,k) &= \sum\limits_{i=1}^{k-1} T(n-i,k-1)-\sum\limits_{i=1}^{k-1} T(n-i,k) \end{align}$$
and also the recurrence:
$$\begin{align} T(n,1) &=1, \\ T(n,2) &= T(n,1)-T(n-1,2),\\ \text{for } k>2, T(n,k) &= \sum\limits_{i=1}^{k-1} T(n-i,k-1) -\sum\limits_{i=1}^{k-1} T(n-i,k) \end{align}$$ which is the same as the first recurrence in the beginning of the question except that the first column here is equal to 1,1,1...
Edit 28.3.2014:
(*Mathematica Mats Granvik 28.3.2014*)
Clear[A, t, n, k, a, nn];
nn = 8;
a = Table[StringJoin[{"x", ToString[n]}], {n, 1, nn}]
Length[a]
t[n_, 1] := t[n, 1] = a[[n]];
t[n_, k_] :=
t[n, k] =
If[And[n > 1, k > 1],
If[k == 2, t[n, k - 1] - t[n - 1, k],
Sum[t[n - i, k - 1], {i, 1, k - 1}] -
Sum[t[n - i, k], {i, 1, k - 1}]], 0];
A = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A]
MatrixForm[a[[1]]*Inverse[A]]
Outputs: 1,-1,-1,0,-1,1,-1,0,...
Edit 7.4.2013:
Input: {"x0", "x1", "x2", "x3", "x4", "x5", "x6", "x7", "x8", "x9", "x10"}
Mathematica program:
(*Mathematica Mats Granvik 7.4.2014*)
Clear[A, t, n, k, a, nn];
nn = 11;
a = Table[StringJoin[{"x", ToString[n - 1]}], {n, 1, nn}]
Length[a]
t[n_, 1] := t[n, 1] = If[n <= 3, 1, a[[n]]];
t[n_, k_] :=
t[n, k] =
If[n >= k,
If[n <= 3, 1,
If[And[k > 1],
If[Or[k == 2, k == 3],
t[n, k - 1] - Sum[t[n - i, k], {i, 1, k - 1}],
If[k >= 4,
Sum[t[n - i, k - 1], {i, 1, k - 2}] -
Sum[t[n - i, k], {i, 1, k - 1}], 0], 0], 0, 0], 0], 0];
A = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A]
Inverse[A][[2 ;; nn, 1]]
Output; {-1, 0, -1, -1, -2, -1, -2, -2, -2, -1}
Which is the Mertens function with the first term negated.
Edit 21.7.2014:
The matrix inverse of this triangle:
$$\left( \begin{array}{cccccc} x_1 & 0 & 0 & 0 & 0 & 0 \\ x_2 & x_2 & 0 & 0 & 0 & 0 \\ x_3 & x_3-x_2 & x_2 & 0 & 0 & 0 \\ x_4 & x_2-x_3+x_4 & x_3-x_2 & x_2 & 0 & 0 \\ x_5 & -x_2+x_3-x_4+x_5 & x_4-x_3 & x_3-x_2 & x_2 & 0 \\ x_6 & x_2-x_3+x_4-x_5+x_6 & x_2-x_4+x_5 & x_4-x_3 & x_3-x_2 & x_2 \end{array} \right)$$
gives the möbius function function divided by $x_1$.
Edit 24.7.2014:
(*Program start*)
(*Mathematica Mats Granvik 24.7.2014*)
Clear[A, t, n, k, a, nn];
nn = 32;
Print["Random numbers as input:"]
a = RandomReal[7, nn]
Length[a];
t[n_, 1] := t[n, 1] = a[[n]];
t[n_, k_] :=
t[n, k] =
If[And[n > 1, k > 1],
If[k == 2, t[n, k - 1] - t[n - 1, k],
Sum[t[n - i, k - 1], {i, 1, k - 1}] -
Sum[t[n - i, k], {i, 1, k - 1}]], 0];
A = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A];
B = a[[1]]*Inverse[A];
Print["Möbius function as output:"]
MatrixForm[B];
Chop[B[[All, 1]]]
(*program end*)