Return to Answer

For simplicity, I assume that $t$ is fixed and omit it as the second index in $T$.

First, let's focus on initial terms with $n\leq t$, for which $$T_n = \sum_{k=0}^{n-1} T_k T_{(t-1-k)\bmod n},$$ implying in particular that $T_1 = 1$ and $$T_t = \sum_{k=0}^{t-1} T_k T_{t-1-k}.$$

Let $$p(x) := \sum_{n=0}^{t-1} T_n x^n$$ be the generating polynomial for the initial terms.

For $n\geq t$, we have \begin{split} T_n &= \sum_{k=0}^{t-1} T_k T_{t-1-k} + \sum_{k=t}^{n-1} T_k T_{n-1+t-k} \\ & = T_t + \sum_{k=0}^{n+t-1} T_k T_{n-1+t-k} - \sum_{k=0}^{t-1} T_k T_{n-1+t-k} - \sum_{k=n}^{n+t-1} T_k T_{n-1+t-k}\\ & = T_t + \sum_{k=0}^{n+t-1} T_k T_{n-1+t-k} - 2\sum_{k=0}^{t-1} T_k T_{n-1+t-k}\\ \end{split}

Let $F(x):=\sum_{n\geq 0} T_n x^n$ be the generating function, and $q(x)$ be the polynomial formed by the initial terms of degree $<2t-1$ from $F(x)^2$ and $r(x)$ be a similar polynomial from $F(x)p(x)$. Considering the terms of degree $<2t-1$ in $$F(x)^2 = (F(x)-p(x)+p(x))^2 = (F(x)-p(x))^2 + 2(F(x)-p(x))F(x) + p(x)^2,$$ we obtain the identity: $$(\star)\qquad q(x) - 2r(x) + p(x)^2\equiv 0.$$

Then the recurrence for $T_n$ with $n\geq t$ translates into $$x^{t-1}(F(x) - p(x)) = T_t\frac{x^{2t-1}}{1-x} + (F(x)^2 - q(x)) - 2(F(x)p(x)-r(x)),$$ which is a quadratic equation for $F(x)$. Solving it and using $(\star)$, we get an explicit expression for the generating function: \begin{split} F(x) &= p(x)+\frac{1}{2}x^{t-1} - \sqrt{p(x)^2+\frac{1}{4}x^{2t-2}+q(x)-2r(x)-T_t\frac{x^{2t-1}}{1-x}} \\ &= p(x)+\frac{1}{2}x^{t-1}\big(1 - \sqrt{\frac{1-(4T_t+1)x}{1-x}}\big). \end{split}

Example for $t=1$. In this case, $T_t=1$ and $p(x)=1$, implying that $$F(x) = \frac12\big(3-\sqrt{\frac{1-5x}{1-x}}\big).$$

Example for $t=2$. In this case, $T_t=2$ and $p(x)=1+x$, implying that $$F(x) = 1 + \frac{x}{2}\big( 3 - \sqrt{\frac{1-9x}{1-x}}\big).$$

Example for $t=3$. In this case, $T_t=5$ and $p(x)=1+x+2x^2$, implying that $$F(x) = 1 + x + x^2\big(5-\sqrt{\frac{1-21x}{1-x}}\big).$$

Just for the record, the sequence of $T_t$ for $t=0,1,2,\dots$ starts with $$1, 1, 2, 5, 14, 50, 194, 1319, 8834, 117869, 1269734, 560616089, \dots$$

For simplicity, I assume that $t$ is fixed and omit it as the second index in $T$.

First, let's focus on initial terms with $n\leq t$, for which $$T_n = \sum_{k=0}^{n-1} T_k T_{(t-1-k)\bmod n},$$ implying in particular that $T_1 = 1$ and $$T_t = \sum_{k=0}^{t-1} T_k T_{t-1-k}.$$

Let $$p(x) := \sum_{n=0}^{t-1} T_n x^n$$ be the generating polynomial for the initial terms.

For $n\geq t$, we have \begin{split} T_n &= \sum_{k=0}^{t-1} T_k T_{t-1-k} + \sum_{k=t}^{n-1} T_k T_{n-1+t-k} \\ & = T_t + \sum_{k=0}^{n+t-1} T_k T_{n-1+t-k} - \sum_{k=0}^{t-1} T_k T_{n-1+t-k} - \sum_{k=n}^{n+t-1} T_k T_{n-1+t-k}\\ & = T_t + \sum_{k=0}^{n+t-1} T_k T_{n-1+t-k} - 2\sum_{k=0}^{t-1} T_k T_{n-1+t-k}\\ \end{split}

Let $F(x):=\sum_{n\geq 0} T_n x^n$ be the generating function, and $q(x)$ be the polynomial formed by the initial terms of degree $<2t-1$ from $F(x)^2$ and $r(x)$ be a similar polynomial from $F(x)p(x)$. Considering the terms of degree $<2t-1$ in $$F(x)^2 = (F(x)-p(x)+p(x))^2 = (F(x)-p(x))^2 + 2(F(x)-p(x))F(x) + p(x)^2,$$ we obtain the identity: $$(\star)\qquad q(x) - 2r(x) + p(x)^2\equiv 0.$$

Then the recurrence for $T_n$ with $n\geq t$ translates into $$x^{t-1}(F(x) - p(x)) = T_t\frac{x^{2t-1}}{1-x} + (F(x)^2 - q(x)) - 2(F(x)p(x)-r(x)),$$ which is a quadratic equation for $F(x)$. Solving it and using $(\star)$, we get an explicit expression for the generating function: \begin{split} F(x) &= p(x)+\frac{1}{2}x^{t-1} - \sqrt{p(x)^2+\frac{1}{4}x^{2t-2}+q(x)-2r(x)-T_t\frac{x^{2t-1}}{1-x}} \\ &= p(x)+\frac{1}{2}x^{t-1}\big(1 - \sqrt{\frac{1-(4T_t+1)x}{1-x}}\big). \end{split}

Example for $t=1$. In this case, $T_t=1$ and $p(x)=1$, implying that $$F(x) = \frac12\big(3-\sqrt{\frac{1-5x}{1-x}}\big).$$

Example for $t=2$. In this case, $T_t=2$ and $p(x)=1+x$, implying that $$F(x) = 1 + \frac{x}{2}\big( 3 - \sqrt{\frac{1-9x}{1-x}}\big).$$

Example for $t=3$. In this case, $T_t=5$ and $p(x)=1+x+2x^2$, implying that $$F(x) = 1 + x + \frac{x^2}2\big(5-\sqrt{\frac{1-21x}{1-x}}\big).$$

Just for the record, the sequence of $T_t$ for $t=0,1,2,\dots$ starts with $$1, 1, 2, 5, 14, 50, 194, 1319, 8834, 117869, 1269734, 560616089, \dots$$

For simplicity, I assume that $t$ is fixed and omit it as the second index in $T$.

First, let's focus on initial terms with $n\leq t$, for which $$T_n = \sum_{k=0}^{n-1} T_k T_{(t-1-k)\bmod n},$$ implying in particular that $T_1 = 1$ and $$T_t = \sum_{k=0}^{t-1} T_k T_{t-1-k}.$$

Let $$p(x) := \sum_{n=0}^{t-1} T_n x^n$$ be the generating polynomial for the initial terms.

For $n\geq t$, we have \begin{split} T_n &= \sum_{k=0}^{t-1} T_k T_{t-1-k} + \sum_{k=t}^{n-1} T_k T_{n-1+t-k} \\ & = T_t + \sum_{k=0}^{n+t-1} T_k T_{n-1+t-k} - \sum_{k=0}^{t-1} T_k T_{n-1+t-k} - \sum_{k=n}^{n+t-1} T_k T_{n-1+t-k}\\ & = T_t + \sum_{k=0}^{n+t-1} T_k T_{n-1+t-k} - 2\sum_{k=0}^{t-1} T_k T_{n-1+t-k}\\ \end{split}

Let $F(x):=\sum_{n\geq 0} T_n x^n$ be the generating function, and $q(x)$ be the polynomial formed by the initial terms of degree $<2t-1$ from $F(x)^2$ and $r(x)$ be a similar polynomial from $F(x)p(x)$.

Then the recurrence for $T_n$ with $n\geq t$ translates into $$x^{t-1}(F(x) - p(x)) = T_t\frac{x^{2t-1}}{1-x} + (F(x)^2 - q(x)) - 2(F(x)p(x)-r(x)),$$ which is a quadratic equation for $F(x)$. Solving it, we get an explicit expression for the generating function: $$F(x) = p(x)+\frac{1}{2}x^{t-1} - \sqrt{p(x)^2+\frac{1}{4}x^{2t-2}+q(x)-2r(x)-T_t\frac{x^{2t-1}}{1-x}}.$$

Example for $t=1$. In this case, $T_t=1$, $p(x)=q(x)=r(x)=1$, implying that $$F(x) = \frac12\big(3-\sqrt{\frac{1-5x}{1-x}}\big).$$

Example for $t=2$. In this case, $T_t=2$, $p(x)=1+x$, $q(x)=1+2x+5x^2$, and $r(x)=1+2x+3x^2$, implying that $$F(x) = 1 + \frac{x}{2}\big( 3 - \sqrt{\frac{1-9x}{1-x}}\big).$$

Example for $t=3$. In this case, $T_t=5$, $p(x)=1+x+2x^2$, $q(x)=1 + 2x + 5x^2 + 14x^3 + 74x^4$, and $r(x)=1 + 2x + 5x^2 + 9x^3 + 39x^4$, implying that $$F(x) = 1 + x + x^2\big(5-\sqrt{\frac{1-21x}{1-x}}\big).$$

The examples suggest

Conjecture. For any $t$, the generating function for $T_k$ has the form: $$F(x) = p(x) + \frac{x^{t-1}}{2}\big(1 - \sqrt{\frac{1-(4T_t+1)x}{1-x}}\big).$$

The sequence of $T_t$ for $t=1,2,\dots$ starts with $$1, 2, 5, 14, 50, 194, 1319, 8834, 117869, 1269734, 560616089, \dots$$ giving the corresponding sequence of coefficients $4T_t+1$: $$5, 9, 21, 57, 201, 777, 5277, 35337, 471477, 5078937, 2242464357, \dots$$

For simplicity, I assume that $t$ is fixed and omit it as the second index in $T$.

First, let's focus on initial terms with $n\leq t$, for which $$T_n = \sum_{k=0}^{n-1} T_k T_{(t-1-k)\bmod n},$$ implying in particular that $T_1 = 1$ and $$T_t = \sum_{k=0}^{t-1} T_k T_{t-1-k}.$$

Let $$p(x) := \sum_{n=0}^{t-1} T_n x^n$$ be the generating polynomial for the initial terms.

For $n\geq t$, we have \begin{split} T_n &= \sum_{k=0}^{t-1} T_k T_{t-1-k} + \sum_{k=t}^{n-1} T_k T_{n-1+t-k} \\ & = T_t + \sum_{k=0}^{n+t-1} T_k T_{n-1+t-k} - \sum_{k=0}^{t-1} T_k T_{n-1+t-k} - \sum_{k=n}^{n+t-1} T_k T_{n-1+t-k}\\ & = T_t + \sum_{k=0}^{n+t-1} T_k T_{n-1+t-k} - 2\sum_{k=0}^{t-1} T_k T_{n-1+t-k}\\ \end{split}

Let $F(x):=\sum_{n\geq 0} T_n x^n$ be the generating function, and $q(x)$ be the polynomial formed by the initial terms of degree $<2t-1$ from $F(x)^2$ and $r(x)$ be a similar polynomial from $F(x)p(x)$. Considering the terms of degree $<2t-1$ in $$F(x)^2 = (F(x)-p(x)+p(x))^2 = (F(x)-p(x))^2 + 2(F(x)-p(x))F(x) + p(x)^2,$$ we obtain the identity: $$(\star)\qquad q(x) - 2r(x) + p(x)^2\equiv 0.$$

Then the recurrence for $T_n$ with $n\geq t$ translates into $$x^{t-1}(F(x) - p(x)) = T_t\frac{x^{2t-1}}{1-x} + (F(x)^2 - q(x)) - 2(F(x)p(x)-r(x)),$$ which is a quadratic equation for $F(x)$. Solving it and using $(\star)$, we get an explicit expression for the generating function: \begin{split} F(x) &= p(x)+\frac{1}{2}x^{t-1} - \sqrt{p(x)^2+\frac{1}{4}x^{2t-2}+q(x)-2r(x)-T_t\frac{x^{2t-1}}{1-x}} \\ &= p(x)+\frac{1}{2}x^{t-1}\big(1 - \sqrt{\frac{1-(4T_t+1)x}{1-x}}\big). \end{split}

Example for $t=1$. In this case, $T_t=1$ and $p(x)=1$, implying that $$F(x) = \frac12\big(3-\sqrt{\frac{1-5x}{1-x}}\big).$$

Example for $t=2$. In this case, $T_t=2$ and $p(x)=1+x$, implying that $$F(x) = 1 + \frac{x}{2}\big( 3 - \sqrt{\frac{1-9x}{1-x}}\big).$$

Example for $t=3$. In this case, $T_t=5$ and $p(x)=1+x+2x^2$, implying that $$F(x) = 1 + x + x^2\big(5-\sqrt{\frac{1-21x}{1-x}}\big).$$

Just for the record, the sequence of $T_t$ for $t=0,1,2,\dots$ starts with $$1, 1, 2, 5, 14, 50, 194, 1319, 8834, 117869, 1269734, 560616089, \dots$$

For simplicity, I assume that $t$ is fixed and omit it as the second index in $T$.

First, let's focus on initial terms with $n\leq t$, for which $$T_n = \sum_{k=0}^{n-1} T_k T_{(t-1-k)\bmod n},$$ implying in particular that $T_1 = 1$ and $$T_t = \sum_{k=0}^{t-1} T_k T_{t-1-k}.$$

Let $$p(x) := \sum_{n=0}^{t-1} T_n x^n$$ be the generating polynomial for the initial terms.

For $n\geq t$, we have \begin{split} T_n &= \sum_{k=0}^{t-1} T_k T_{t-1-k} + \sum_{k=t}^{n-1} T_k T_{n-1+t-k} \\ & = T_t + \sum_{k=0}^{n+t-1} T_k T_{n-1+t-k} - \sum_{k=0}^{t-1} T_k T_{n-1+t-k} - \sum_{k=n}^{n+t-1} T_k T_{n-1+t-k}\\ & = T_t + \sum_{k=0}^{n+t-1} T_k T_{n-1+t-k} - 2\sum_{k=0}^{t-1} T_k T_{n-1+t-k}\\ \end{split}

Let $F(x):=\sum_{n\geq 0} T_n x^n$ be the generating function, and $q(x)$ be the polynomial formed by the initial terms of degree $<2t-1$ from $F(x)^2$ and $r(x)$ be a similar polynomial from $F(x)p(x)$.

Then the recurrence for $T_n$ with $n\geq t$ translates into $$x^{t-1}(F(x) - p(x)) = T_t\frac{x^{2t-1}}{1-x} + (F(x)^2 - q(x)) - 2(F(x)p(x)-r(x)),$$ which is a quadratic equation for $F(x)$. Solving it, we get an explicit expression for the generating function: $$F(x) = p(x)+\frac{1}{2}x^{t-1} - \sqrt{p(x)^2+\frac{1}{4}x^{2t-2}+q(x)-2r(x)-T_t\frac{x^{2t-1}}{1-x}}.$$

Example for $t=1$. In this case, $T_t=1$, $p(x)=q(x)=r(x)=1$, implying that $$F(x) = \frac12\big(3-\sqrt{\frac{1-5x}{1-x}}\big).$$

Example for $t=2$. In this case, $T_t=2$, $p(x)=1+x$, $q(x)=1+2x+5x^2$, and $r(x)=1+2x+3x^2$, implying that $$F(x) = 1 + \frac{x}{2}\big( 3 - \sqrt{\frac{1-9x}{1-x}}\big).$$

Example for $t=3$. In this case, $T_t=5$, $p(x)=1+x+2x^2$, $q(x)=1 + 2x + 5x^2 + 14x^3 + 74x^4$, and $r(x)=1 + 2x + 5x^2 + 9x^3 + 39x^4$, implying that $$F(x) = 1 + x + x^2\big(5-\sqrt{\frac{1-21x}{1-x}}\big).$$

The examples suggest

Conjecture. For any $t$, the generating function for $T_k$ has the form: $$F(x) = p(x) + \frac{x^{t-1}}{2}\big(1 - \sqrt{\frac{1-C_tx}{1-x}}\big),$$ where $C_t$ is a constant coefficient depending on $t$.

The sequence of $C_t$ for $t=1,2,\dots$ starts with $$5, 9, 21, 57, 201, 777, 5277, 35337, 471477, 5078937, 2242464357, \dots$$

For simplicity, I assume that $t$ is fixed and omit it as the second index in $T$.

First, let's focus on initial terms with $n\leq t$, for which $$T_n = \sum_{k=0}^{n-1} T_k T_{(t-1-k)\bmod n},$$ implying in particular that $T_1 = 1$ and $$T_t = \sum_{k=0}^{t-1} T_k T_{t-1-k}.$$

Let $$p(x) := \sum_{n=0}^{t-1} T_n x^n$$ be the generating polynomial for the initial terms.

For $n\geq t$, we have \begin{split} T_n &= \sum_{k=0}^{t-1} T_k T_{t-1-k} + \sum_{k=t}^{n-1} T_k T_{n-1+t-k} \\ & = T_t + \sum_{k=0}^{n+t-1} T_k T_{n-1+t-k} - \sum_{k=0}^{t-1} T_k T_{n-1+t-k} - \sum_{k=n}^{n+t-1} T_k T_{n-1+t-k}\\ & = T_t + \sum_{k=0}^{n+t-1} T_k T_{n-1+t-k} - 2\sum_{k=0}^{t-1} T_k T_{n-1+t-k}\\ \end{split}

Let $F(x):=\sum_{n\geq 0} T_n x^n$ be the generating function, and $q(x)$ be the polynomial formed by the initial terms of degree $<2t-1$ from $F(x)^2$ and $r(x)$ be a similar polynomial from $F(x)p(x)$.

Then the recurrence for $T_n$ with $n\geq t$ translates into $$x^{t-1}(F(x) - p(x)) = T_t\frac{x^{2t-1}}{1-x} + (F(x)^2 - q(x)) - 2(F(x)p(x)-r(x)),$$ which is a quadratic equation for $F(x)$. Solving it, we get an explicit expression for the generating function: $$F(x) = p(x)+\frac{1}{2}x^{t-1} - \sqrt{p(x)^2+\frac{1}{4}x^{2t-2}+q(x)-2r(x)-T_t\frac{x^{2t-1}}{1-x}}.$$

Example for $t=1$. In this case, $T_t=1$, $p(x)=q(x)=r(x)=1$, implying that $$F(x) = \frac12\big(3-\sqrt{\frac{1-5x}{1-x}}\big).$$

Example for $t=2$. In this case, $T_t=2$, $p(x)=1+x$, $q(x)=1+2x+5x^2$, and $r(x)=1+2x+3x^2$, implying that $$F(x) = 1 + \frac{x}{2}\big( 3 - \sqrt{\frac{1-9x}{1-x}}\big).$$

Example for $t=3$. In this case, $T_t=5$, $p(x)=1+x+2x^2$, $q(x)=1 + 2x + 5x^2 + 14x^3 + 74x^4$, and $r(x)=1 + 2x + 5x^2 + 9x^3 + 39x^4$, implying that $$F(x) = 1 + x + x^2\big(5-\sqrt{\frac{1-21x}{1-x}}\big).$$

The examples suggest

Conjecture. For any $t$, the generating function for $T_k$ has the form: $$F(x) = p(x) + \frac{x^{t-1}}{2}\big(1 - \sqrt{\frac{1-(4T_t+1)x}{1-x}}\big).$$

The sequence of $T_t$ for $t=1,2,\dots$ starts with $$1, 2, 5, 14, 50, 194, 1319, 8834, 117869, 1269734, 560616089, \dots$$ giving the corresponding sequence of coefficients $4T_t+1$: $$5, 9, 21, 57, 201, 777, 5277, 35337, 471477, 5078937, 2242464357, \dots$$