### A product rule for triangular numbers, part 4

In our previous posts, we found five sequences that satisfy

T(mn) = T(m) T(n) + T(m-1) T(n-1).

We list these sequences below for ease of reference.

• 1/2, 1/2, 1/2, 1/2, 1/2, …  (Constant sequence)
• 0, 0, 0, 0, 0, 0, 0, 0, 0, … (Zero sequence)
• 0, 1, 0, 0, 1, 0, 0, 1, 0, … (Repeats with period 3)
• 0, 1, 1, 2, 2, 3, 3, 4, 4, … (Round n/2 up to the nearest integer)
• 0, 1, 3, 6, 10, 15, 21, …   (Triangular numbers)

We will show that there are no other sequences that satisfy the recurrence. Since we have already shown that T(n) = 1/2 is the only solution that satisfies T(0) ≠ 0, we will assume henceforth that T(0) = 0.

Lemma 1. If T(0) = 0 and T(n)  0 for some n > 0, then T(1) = 1.

Proof. Suppose that T(n) 0 for some n > 0. Then

T(n) = T(n) T(1) + T(n-1) T(0) = T(n) T(1),

and we obtain T(1) = 1 by dividing both sides by T(n).

Lemma 2. If T(0) = 0 and T(1) = 1, then T(n) is uniquely determined by T(2) and T(3) for all n > 3.

Proof. Let a = T(2) and b = T(3). Then

T(2n) = T(2) T(n) + T(1) T(n-1) = aT(n) + T(n-1)
T(4) = T(2) T(2) + T(1) T(1) = a2 + 1
T(4n) = T(4) T(n) + T(3) T(n-1) = (a2 + 1) T(n) + bT(n-1)
T(4n) = T(2) T(2n) + T(1) T(2n-1) = aT(2n) + T(2n-1).

Combining these equations yields

T(2n-1) = T(4n) – aT(2n)
= (a2 + 1) T(n) + bT(n-1) – a2T(n) – aT(n-1)
= T(n) + (b – a) T(n-1).

Since T(2n) and T(2n-1) are linear combinations of previous terms for all n > 2, and the coefficients are functions of a and b, it follows that T(n) is uniquely determined by T(2) and T(3) for all n > 3.

Lemma 3. If T(0) = 0 and T(1) = 1, then T(n) is uniquely determined by T(2) for all n > 2.

Proof. As before, let a = T(2) and b = T(3). By the previous lemma, it suffices to express b in terms of a.

T(4) = a2 + 1
T(5) = T(3) + (b – a) T(2) = b + ab – a2
T(6) = T(2) T(3) + T(1) T(2) = ab + a
T(8) = T(2) T(4) + T(1) T(3) = a(a2 + 1) + b = a3 + a + b
T(9) = T(3) T(3) + T(2) T(2) = a2 + b2
T(18) = T(3) T(6) + T(2) T(5) = b(ab + a) + a(b + ab – a2)
T(18) = T(2) T(9) + T(1) T(8) = a(a2 + b2) + (a3 + a + b)

Equating the two expressions for T(18) yields

(a2 + 2a – 1) b = 3a3 + a.

If a2 + 2a – 1 = 0, then 3a3 + a  ≠ 0, which is a contradiction. Therefore,

$b = \displaystyle \frac{3a^3 + a}{a^2 + 2a - 1}$.

Lemma 4. If T(0) = 0 and T(1) = 1, then T(2) = 0, 1, or 3.

By Lemma 2 and Lemma 3, we may define T(n) by the following formulas.

T(2) = a
T(3) = b = (3a3 + a) / (a2 + 2a – 1)
T(2n) =  aT(n) + T(n – 1)
T(2n-1) = T(n) + (b – a) T(n – 1)

The Maple code listed below implements these formulas.

T[1] := 1;
T[2] := a;
b := (3*a^3+a)/(a^2+2*a-1);
T[3] := b;
for n from 4 to 20 do
k := ceil(n/2);
if n mod 2 = 0 then
T[n] := normal(a*T[k]+T[k-1])
else T[n] := normal(T[k]+(b-a)*T[k-1])
end if
end do;

We use the relations T(9) = T(3) T(3) + T(2) T(2) and T(15) = T(3) T(5) + T(2) T(4) to obtain two equations that must be satisfied by a. The Maple code is listed below.

numer(factor(T[9]-T[3]*T[3]-T[2]*T[2]));
numer(factor(T[15]-T[3]*T[5]-T[2]*T[4]));

This yields the following equations:

$a(a-1)(a-3)(a+1)(2a^3+a-1)=0$
$a(a-1)(a-3)(8a^6-a^5+7a^4-4a^3-3a+1) = 0$

The only common solutions to these equations are 0, 1, and 3.

Conclusion: The recurrence has exactly two solutions which are constant sequences: T(n) = 0 for all n, or T(n) = 1/2 for all n. Any nonconstant solution must satisfy T(0) = 0 and T(1) = 1, and all other terms are uniquely determined by T(2). We showed that T(2) must equal 0, 1, or 3, and we exhibited solutions with each possible value for T(2). Therefore, the recurrence has exactly the five solutions listed at the top of this post.