A product rule for triangular numbers, part 3
by David Radcliffe
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
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!