The natural numbers $1,2,3,4,5....$ can be calculated as the row sums of the triangle $T(n,k)$ equal to $1$ if $n \geq k$ and $0$ otherwise:
$$\displaystyle T = \left(\begin{matrix} 1&0&0&0&0&0&0&\cdots \\ 1&1&0&0&0&0&0 \\ 1&1&1&0&0&0&0 \\ 1&1&1&1&0&0&0 \\ 1&1&1&1&1&0&0 \\ 1&1&1&1&1&1&0 \\ 1&1&1&1&1&1&1 \\ \vdots&&&&&&&\ddots \end{matrix}\right)$$
This table $T$ satisfies the overly complicated recurrence: $$T(n,1) = 1$$ $$\text{If}\; n\geq k \; \text{then} \; T(n,k) = x \sum _{i=1}^{n-1} T(n-i,k-1)+y \sum _{i=1}^{n-1} T(n-i,k) \; \text{else} \; T(n,k) = 0$$
when $x=1$ and $y=-1$
The row sums of the table $T$ when $x=1$ appears to be:
$$A_T(n) = \sum\limits_{k=1}^{k=n} T(n,k) = \lim_{s\to y+1} \, \frac{(s+1)^{n-1}+s-1}{s}$$
as a function of $y$. $x$ not included in the limit above since I don't know what the relationship to $x$ is here when $x$ is unequal to 1.
The number of divisors of $n:$ $1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6....$ can be calculated as the row sums of the triangle $t(n,k)$ equal to $1$ if $k \mid n$ and $0$ otherwise:
$$\displaystyle t = \left(\begin{matrix} 1&0&0&0&0&0&0&\cdots \\ 1&1&0&0&0&0&0 \\ 1&0&1&0&0&0&0 \\ 1&1&0&1&0&0&0 \\ 1&0&0&0&1&0&0 \\ 1&1&1&0&0&1&0 \\ 1&0&0&0&0&0&1 \\ \vdots&&&&&&&\ddots \end{matrix}\right)$$
This table $t$ satisfies again an overly complicated recurrence: $$t(n,1) = 1$$ $$\text{If}\; n\geq k \; \text{then} \; t(n,k) = x \sum _{i=1}^{k-1} t(n-i,k-1)+y \sum _{i=1}^{k-1} t(n-i,k) \; \text{else} \; t(n,k) = 0$$
when $x=1$ and $y=-1$
Where the difference to the first simpler recurrence for matrix $T$ compared to matrix $t$ is that in matrix $T$ the summation index goes to $n-1$ while here in matrix $t$ it goes to $k-1$. Otherwise the same kind of recurrence.
Proof given by Jeffrey Shallit via email:
OK, now I see. You wrote "k" before when you talked about the k previous terms, and you really meant "k-1" previous terms.
Just to let you know: you should have written
t(n,k) = (sum from i = 1 to k-1 of t(n-i,k-1)) - (sum from i = 1 to k-1 of t(n-i,k))
Here's the proof.
Now (sum from i=1 to k-1 of t(n-i,k-1)) is just the number of elements in {n-k+1,...,n-1) that are divisible by k-1. This is always equal to 1, because in k-1 consecutive integers, exactly one will be divisible by k-1.
On the other hand, (sum from i = 1 to k-1 of t(n-i,k)) is equal to either 0 or 1, because in k-1 consecutive integers, either 0 or 1 of them are divisible by k. We get 1 except if all are not divisible by k, which means the next integer /is/ divisible by k, and the next integer is n.
What I have found experimentally is a relationship between;
$$A_T(n) = \sum\limits_{k=1}^{k=n} T(n,k)$$
and;
$$a_t(n) = \sum\limits_{k=1}^{k=n} t(n,k)$$
when;
$x \geq 1$ $y \geq 0$
or;
$x \leq -2$ $y \leq -2$
$$a_t(n) \;\; \sim \;\; \frac{A_T(n)}{c}$$
where:
$$c = \left(\prod _{n=2}^{\text{nn}} \frac{1}{1-\frac{1}{A_T(n)}}\right)$$
Put together:
$$a_t(n) \;\; \sim \;\; \frac{A_T(n)}{\left(\prod _{n=2}^{\text{nn}} \frac{1}{1-\frac{1}{A_T(n)}}\right)}$$
Works also for $x$ and $y$ as some complex numbers but I have not studied for what ranges of complex number it is valid.
Taking the difference between the left hand side ($a_t(n)$) and the right side (the approximation $\frac{A_T(n)}{c}$) I have found, and this is the question:
Is the ratio between the consecutive terms:
$$\lim_{n \to \infty} \left(\frac{a_t(n)-\frac{A_T(n)}{c}}{a_t(n-1)-\frac{A_T(n-1)}{c}}\right) = \frac{1}{2} \left((y+1)+\sqrt{(y+1)^2+4}\right)$$
when $y \geq 1$ and $x=1$?
Mathematica program to demonstrate, where $x=1$ and $y=0$ giving the Pascal triangle and the Mahonian numbers:
Edit 7.1.2015:
Clear[t, n, k, a, b, x, y, b1, at, T, AT, at];
nn = 160;
y = 1;
T[n_, 1] = 1;
T[n_, k_] :=
T[n, k] =
If[n >= k,
Sum[T[n - i, k - 1], {i, 1, n - 1}] +
y*Sum[T[n - i, k], {i, 1, n - 1}], 0];
A = Table[Table[Expand[T[n, k]], {k, 1, nn}], {n, 1, nn}];
(*TableForm[A]*)
a = Total[Transpose[A]];
Print["The sequence 'a' that is the row sums of the recursively \
generated table t[n,k] above:"]
a[[1 ;; 20]]
Print["appears to be equivalent to the sequence f(n, y) = \
Limit[((s+1)^(n-1)+s-1)/s,s\[Rule]y+1]:"]
Table[Limit[((s + 1)^(n - 1) + s - 1)/s, s -> y + 1], {n, 1, 12}]
Clear[t];
t[n_, 1] = 1;
t[n_, k_] :=
t[n, k] =
If[n >= k,
Sum[t[n - i, k - 1], {i, 1, k - 1}] +
y*Sum[t[n - i, k], {i, 1, k - 1}], 0];
B = Table[Table[Expand[t[n, k]], {k, 1, nn}], {n, 1, nn}];
(*TableForm[B]*)
b = Total[Transpose[B]];
Print["The sequence 'b' is the row sums of the second recursively \
generated table t[n,k] above:"]
b[[1 ;; 20]]
Print["Prove or disprove that the ratio between sequence a and b, \
a/b:"]
N[a[[nn]]/b[[nn]], 12]
Print["converges to the constant c = \
Product[1/(1-1/a[[i]]),{i,2,nn}]:"]
c = Product[1/(1 - 1/a[[i]]), {i, 2, nn}];
N[c, 12]
Print["The error (b(n)-1/c)/(b(n)-1/c*a(n)):"]
N[(b[[nn - 1]] - 1/c*a[[nn - 1]])/(b[[nn]] - 1/c*a[[nn]]), 12]^-1
Print["appears to converge to the expression \
1/2*((y+1)+Sqrt[(y+1)^2+4]):"]
N[1/2*((y + 1) + Sqrt[(y + 1)^2 + 4]), 12]
Print["Can this error size also be proven?"]
Edit 22.7.2014:
With this Mathematica program a relation between diagonal sums of $t$ and row sums of $t$ is arrived at in terms of the constant $c$:
Clear[t, n, k, a, b, x, y, b1, at, T, AT, at];
nn = 200;
x = 1;
y = 0;
T[n_, 1] = 1;
T[n_, k_] :=
T[n, k] =
If[n >= k,
x*Sum[T[n - i, k - 1], {i, 1, n - 1}] +
y*Sum[T[n - i, k], {i, 1, n - 1}], 0];
a = Table[Table[Expand[T[n, k]], {k, 1, nn}], {n, 1, nn}];
(*TableForm[a]*)
AT = Total[Transpose[a]];
AT[[1 ;; 20]];
Table[Limit[((s + 1)^(n - 1) + s - 1)/s, s -> y + 1], {n, 1, 12}];
c = Product[1/(1 - 1/AT[[i]]), {i, 2, nn}];
N[c, 12]
Clear[t];
t[n_, 1] = 1;
t[n_, k_] :=
t[n, k] =
If[n >= k,
x*Sum[t[n - i, k - 1], {i, 1, k - 1}] +
y*Sum[t[n - i, k], {i, 1, k - 1}], 0];
a = Table[Table[Expand[t[n, k]], {k, 1, nn}], {n, 1, nn}];
aa = Table[
Total[Table[t[n - k + 1, k], {k, 1, nn}]], {n, 1 + 1, nn + 1}];
(*TableForm[a]*)
at = Total[Transpose[a]];
at[[1 ;; 20]];
N[AT[[nn]]/at[[nn]], 12]
N[aa/(at - 1/c*AT), 30][[nn - 20 ;; nn]]
(*N[1/2*((y+1)+Sqrt[(y+1)^2+4]),12]*)
Second edit 22.7.2014:
A relation to https://oeis.org/A092526 is found in this program:
Clear[t, n, k, a, b, x, y, b1, at, T, AT, at];
nn = 300;
x = 1;
y = 0;
T[n_, 1] = 1;
T[n_, k_] :=
T[n, k] =
If[n >= k,
x*Sum[T[n - i, k - 1], {i, 1, n - 1}] +
y*Sum[T[n - i, k], {i, 1, n - 1}], 0];
a = Table[Table[Expand[T[n, k]], {k, 1, nn}], {n, 1, nn}];
(*TableForm[a]*)
AT = Total[Transpose[a]];
AT[[1 ;; 20]];
Table[Limit[((s + 1)^(n - 1) + s - 1)/s, s -> y + 1], {n, 1, 12}];
c = Product[1/(1 - 1/AT[[i]]), {i, 2, nn}];
N[c, 12]
Clear[t];
t[n_, 1] = 1;
t[n_, k_] :=
t[n, k] =
If[n >= k,
x*Sum[t[n - i, k - 1], {i, 1, k - 1}] +
y*Sum[t[n - i, k], {i, 1, k - 1}], 0];
a = Table[Table[Expand[t[n, k]], {k, 1, nn}], {n, 1, nn}];
aa = Table[
Total[Table[t[n - k + 1, k], {k, 1, nn}]], {n, 1 + 1, nn + 1}];
(*TableForm[a]*)
at = Total[Transpose[a]];
at[[1 ;; 20]];
N[AT[[nn]]/at[[nn]], 12]
N[aa/(at - 1/c*AT), 30][[nn - 20 ;; nn]]
Ratios[N[aa - (at - 1/c*AT), 30][[nn - 20 ;; nn]]]
ListLinePlot[Log[N[aa - (at - 1/c*AT), 30]]]
(*N[1/2*((y+1)+Sqrt[(y+1)^2+4]),12]*)
Output: 1.465571230... Which is close to 1.465571231... which the only real root to the equation: N[Solve[x^3 - 1 x^2 - 1 == 0, x], 20]
Edit 23.7.2014:
Setting the parameter nn = 500, and
y=-1 gives the only real root of N[Solve[-x^3 +0*x^2 + 1 == 0, x], 20] = 1.00000000000000000
y=0 gives the only real root of N[Solve[-x^3 + 1*x^2 + 1 == 0, x], 20] = 1.46557123187676802
y=1 gives the only real root of N[Solve[-x^3 + 2*x^2 + 1 == 0, x], 20] = 2.20556943040059031
y=2 gives the only real root of N[Solve[-x^3 + 3*x^2 + 1 == 0, x], 20] = 3.103803402735536533
y=3 gives the only real root of N[Solve[-x^3 + 4*x^2 + 1 == 0, x], 20] = 4.06064702755414245