mathblag

Musings on mathematics and teaching.

Month: June, 2012

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.

Advertisements

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 β = β2 + α2. 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) = α (β/α)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 T(n) = 1 + 2 + \ldots + n = \frac12 n(n+1). 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)

Triangular numbers

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

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

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

T(20) = T(5)T(4) + T(4)T(3).

Triangular Numbers: T(20) = T(5) T(4) + T(4) T(3)

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.

Misleading Infographics

Fox News recently aired a misleading attack video on President Obama. Other people have rebutted the claims made by the video, but as a math instructor, I would like to call attention to some of the misleading infographics that were used.

Graphic showing increase in national debt

This graphic shows that the US public debt increased from $10 trillion to $15.7 trillion. The artist chose to represent this change by increasing the dimensions of a moneybag by about 57%. But this would increase the volume of the bag by a factor of 4, since 1.573 = 3.87. Even though the numbers are present, a visual impression is created that the debt has quadrupled.

Here is another misleading graphic which was used to show that unemployment had increased from 7.8% to 8.3%.

The relative increase in the jobless rate was about 6%, since (8.3 – 7.8)/7.8 = 0.064. But notice that the top image has 12 silhouettes, while the bottom image has 17 silhouettes. This is an increase in 42%, so the image creates the visual impression that the jobless rate has increased by 42% instead of 6%.

Why do graphic designers produce such misleading graphics? I cannot believe that they are ignorant of mathematics, but they know that dishonest graphics have more visual impact than truthful graphics. They also know that they are unlikely to be called on their distortions, because most people lack the mathematical literacy to catch them. It is vital that math instructors teach students to recognize and critique misleading infographics.

A property of the divisors of 99

James Tanton (@jamestanton) asked an interesting question on Twitter. Which numbers have the property that the reverse of any multiple of them is again a multiple?

It turns out that the numbers with this property are exactly the divisors of 99 (1, 3, 11, 33, and 99). This property of the divisors of 99 is mentioned in the OEIS, but I have been unable to find a proof in the literature (by which I mean Google). To fill this gap, I have written my own proof, but you might wish to try your hand at proving it yourself.

Numbers that divide the reversals of their multiples