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) = a² + 1
T(4n) = T(4) T(n) + T(3) T(n-1) = (a² + 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)
= (a² + 1) T(n) + bT(n-1) – a²T(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) = a² + 1
T(5) = T(3) + (b – a) T(2) = b + ab – a²
T(6) = T(2) T(3) + T(1) T(2) = ab + a
T(8) = T(2) T(4) + T(1) T(3) = a(a² + 1) + b = a³ + a + b
T(9) = T(3) T(3) + T(2) T(2) = a² + b²
T(18) = T(3) T(6) + T(2) T(5) = b(ab + a) + a(b + ab – a²)
T(18) = T(2) T(9) + T(1) T(8) = a(a² + b²) + (a³ + a + b)

Equating the two expressions for T(18) yields

(a² + 2a – 1) b = 3a³ + a.

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

.

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 = (3a³ + a) / (a² + 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:

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.

A product rule for triangular numbers, part 3

In the previous article in our series, we found that the constant sequence T(n) = 1/2 is the only solution to the recurrence

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

that satisfies T(0) ≠ 0. In this article, we will present four solutions that satisfy T(0) = 0.

Solution 1. T(n) = 0 for all n.  Trivial.

Solution 2. T(2n) = T(2n-1) = n for all n.

Case 1: m and n are both even.

T(2a 2b) = T(4ab) = 2ab;
T(2a) T(2b) + T(2a-1) T(2b-1) = ab + ab = 2ab.

Case 2: m is even, n is odd.

T(2a (2b-1)) = T(4ab – 2a) = 2ab – a;
T(2a) T(2b-1) + T(2a-1) T(2b-2) = ab + a(b-1)
= 2ab – a.

Case 3. m and n are both odd.

T((2a-1)(2b-1)) = T(4ab – 2a – 2b + 1)
= 2ab – a – b + 1;
T(2a-1) T(2b-1) + T(2a-2) T(2b-2) = ab + (a-1)(b-1)
= 2ab – a – b + 1.

Solution 3. T(n) = n(n+1)/2, the triangular numbers.

T(m) T(n) + T(m-1) T(n-1)

= [m(m+1)/2] [n(n+1)/2] + [(m-1)m/2] [(n-1)n/2]
= [mn/4] [(m+1)(n+1) + (m-1)(n-1)]
= [mn/4] [mn+m+n+1 + mn-m-n+1]
= [mn/4] [2mn+2]
= mn (mn+1)/2
= T(mn).

Solution 4. T(3n+1) = 1, T(3n) = T(3n+2) = 0.

This solution can be verified by checking all nine cases modulo 3. A more elegant  method is to show that this sequence is just the previous sequence reduced modulo 3.

In the last part, we will show that this list of solutions is complete. Stay tuned!

A product rule for triangular numbers, part 2

In the previous post, we showed that the sequence of triangular numbers satisfies the product rule

T(mn) = T(m) T(n) + T(m − 1) T(n − 1);    m, n ≥ 1.

Let α = T(0) and β = T(1). We will assume in this post that α ≠ 0. The case α = 0 is more difficult, and will be discussed in parts 3 and 4 of this series.

Substituting m = 1 and n = 1 into the product rule gives β = β² + α². Since α ≠ 0, it follows that β ≠ 1, so we can rewrite the above equation as

α/(1 – β) = β/α .

Substituting m = 1 into the product rule gives T(n) = βT(n) + αT(n-1), hence

T(n)/T(n-1) =  α/(1 – β) = β/α .

Therefore,

T(n) = α (β/α)ⁿ   for all n ≥ 0.

That is to say that T(n) is a geometric sequence. But a geometric sequence cannot satisfy the product rule unless it is a constant sequence (see the comments), in which case α = 1/2.

Therefore, the only solution to T(mn) = T(m) T(n) + T(m-1) T(n-1) satisfying T(0) ≠ 0 is the constant sequence T(n) = 1/2.

I am grateful to an anonymous commenter for pointing out a major error in a previous version of this post.

A product rule for triangular numbers

The nth triangular number is . It represents the number of dots in a triangular arrangement, with 1 dot in the first row, 2 dots in the second row, etc. (Image source: Wikipedia)

The triangular numbers satisfy many interesting properties, including a product rule:

This rule can be demonstrated visually by subdividing a triangle into smaller triangles. The following picture illustrates the case

.

Inspired by a question of James Tanton, I sought to find all sequences that satisfy this product rule. This problem has a lovely solution, and I encourage you to discover it for yourself. I will outline my solution in subsequent posts.