# Prove that this sequence of fractions is returned unchanged after the divisor recurrence, the matrix inverse, and the sum over divisors.

Consider the fraction of binomial coefficients and powers of $4$:

$$a(n)=\frac{\binom{2 (n-1)}{n-1}}{4^{n-1}}$$

starting:

$$1,\frac{1}{2},\frac{3}{8},\frac{5}{16},\frac{35}{128},\frac{63}{256},\frac{231}{1024},\frac{429}{2048},\frac{6435}{32768},\frac{12155}{65536},...$$

Let the fraction be the first column in a matrix defined by the recurrence:

$$t(n,1) = a(n)$$

$$\text{If}\; n\geq k \; \text{then} \; t(n,k) = \sum _{i=1}^{k-1} t(n-i,k-1)-\sum _{i=1}^{k-1} t(n-i,k) \; \text{else} \; t(n,k) = 0$$

This is the table $T$ starting:

$$T=\left( \begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{2} & 1 & 0 & 0 & 0 & 0 & 0 \\ \frac{3}{8} & -\frac{1}{2} & 1 & 0 & 0 & 0 & 0 \\ \frac{5}{16} & \frac{7}{8} & -\frac{1}{2} & 1 & 0 & 0 & 0 \\ \frac{35}{128} & -\frac{9}{16} & -\frac{1}{8} & -\frac{1}{2} & 1 & 0 & 0 \\ \frac{63}{256} & \frac{107}{128} & \frac{15}{16} & -\frac{1}{8} & -\frac{1}{2} & 1 & 0 \\ \frac{231}{1024} & -\frac{151}{256} & -\frac{69}{128} & -\frac{1}{16} & -\frac{1}{8} & -\frac{1}{2} & 1 \end{array} \right)$$

Then calculate the matrix inverse $U$ starting:

$$U=\left( \begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ -\frac{1}{2} & 1 & 0 & 0 & 0 & 0 & 0 \\ -\frac{5}{8} & \frac{1}{2} & 1 & 0 & 0 & 0 & 0 \\ -\frac{3}{16} & -\frac{5}{8} & \frac{1}{2} & 1 & 0 & 0 & 0 \\ -\frac{93}{128} & \frac{5}{16} & \frac{3}{8} & \frac{1}{2} & 1 & 0 & 0 \\ \frac{95}{256} & -\frac{157}{128} & -\frac{11}{16} & \frac{3}{8} & \frac{1}{2} & 1 & 0 \\ -\frac{793}{1024} & \frac{63}{256} & \frac{35}{128} & \frac{5}{16} & \frac{3}{8} & \frac{1}{2} & 1 \end{array} \right)$$

Then take the sequence in the first column of $U$, call it $b(n)$, starting:

$$1,-\frac{1}{2},-\frac{5}{8},-\frac{3}{16},-\frac{93}{128},\frac{95}{256},-\frac{793}{1024},...$$

Sum $b(n)$ over the divisors:

$$\sum\limits_{d\mid n} b(d)=a(n)$$

and you get the same sequence $a(n)$ that we started with:

$$1,\frac{1}{2},\frac{3}{8},\frac{5}{16},\frac{35}{128},\frac{63}{256},\frac{231}{1024},\frac{429}{2048},\frac{6435}{32768},\frac{12155}{65536},...$$

How can this be? Can you prove it?

As a Mathematica program this is:

Clear[t, nn]
nn = 7;
t[n_, 1] := t[n, 1] = Binomial[2 (n - 1), (n - 1)]/4^(n - 1);
t[n_, k_] :=
t[n, k] =
If[n >= k,
Sum[t[n - i, k - 1], {i, 1, k - 1}] -
Sum[t[n - i, k], {i, 1, k - 1}], 0]
T = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
Table[T[[n, 1]], {n, 1, nn}]
MatrixForm[T];
U = Inverse[T];
MatrixForm[U];
Table[Sum[If[Mod[n, k] == 0, U[[n/k, 1]], 0], {k, 1, nn}], {n, 1, nn}]
CoefficientList[Series[1/Sqrt[1 - x], {x, 0, nn - 1}], x]


The sequence $a(n)$ is also the coefficients of the series expansion of $$\frac{1}{\sqrt{1-x}}$$.

http://pastebin.com/Xdt2Eg3B