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*)