What Are Narayana's Cows and Why Do They Have a Sequence?
Two hundred years after Italian mathematician Leonardo of Pisa came up with his Fibonacci sequence while considering the breeding of immortal rabbits, Indian mathematician Narayana Pandit came up with another sequence involving the breeding of immortal cows.
The nth term of the Fibonacci sequence gives the number of rabbit pairs after n generations when it is assumed that a rabbit can begin breeding in its third year and breed every year after that. Each rabbit pair of reproductive age is assumed to produce one pair of bunnies each year and never dies. With these conditions it is easy to see that the Fibonacci sequence is generated by the recurrence F(n) = F(n-1) + F(n-2). If you start with a single pair, the sequences progresses as 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...
In the same vein, the nth term of Narayana's cows sequence gives the number of pairs of cows after n generations when it is assumed that pairs can begin breeding in their fourth year, and breed every year after. As with Fibonacci's rabbits, each cow pair is assumed to produce one pair of calves each year and never dies. Letting C(n) be the number of cow pairs after n generations, these conditions give the recurrence formula C(n) = C(n-1) + C(n-3). If you start with a single pair of cows, the sequence progresses as 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41,...
Just as the Fibonacci sequence has many amazing mathematical properties, so does Narayana's cows sequence.
Curious Properties of Narayana's Cows Numbers
If you let C(1) = C(2) = C(3) = 1, then the first 20 terms of Narayana's cows sequence are 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872,...
Even though the sequence is defined by the recurrence relation C(n) = C(n-1) + C(n-3), it also satisfies several other recurrences. For example, if you sum three consecutive terms in the progression, you get another term two places ahead in the sequence. In other words, it satisfies the recurrence C(n) = C(n-2) + C(n-3) + C(n-4). It also satisfies the following linear recurrences:
- C(n) = C(n-2) + 2*C(n-4) + C(n-6)
- C(n) = 2*C(n-3) + C(n-4) + C(n-5)
- C(n) = 3*C(n-4) + C(n-5) + 2*C(n-6)
It is possible to work backwards to compute negative indexed terms. The first term you get working backwards is C(0) = 0, followed by C(-1) = 0, and C(-2) = 0. Here are the non-positive indexed terms from n = 0 to n = -30:
0, 0, 1, 0, -1, 1, 1, -2, 0, 3, -2, -3, 5, 1, -8, 4, 9, -12, -5, 21, -7, -26, 28, 19, -54, 9, 73, -63, -64, 136, 1,...
By letting the sequence run backwards you can devise some non-linear recurrence formulas:
- C(n)^2 - C(n-1)*C(n+1) = C(-n-1)
- C(n+2)*C(n-1) - C(n+1)*C(n) = C(-n-3)
In comparison, when you run the Fibonacci sequence backwards you get the Fibonacci numbers with alternating signs. The signs of the reverse Narayana's cows sequence to not alternate in a fixed pattern.
However, like the Fibonacci sequence the reverse terms of the Narayana's cows sequences are all integers, something that isn't true with recursive sequences in general. Also like the Fibonacci numbers, the sequence of differences of Narayana's cows numbers returns the same sequence.
More Mathematical Properties of Narayana's Cows Sequence
- For every integer k, there exists a Narayana's Cows number that is divisible by k. The same is true of the Fibonacci numbers and the proofs of these facts are similar, using the concept of Pisano periods. This is not true in general for integer sequences, which means both the Fibonacci numbers and Narayana's Cows numbers are very special.
- The ratio between consecutive terms in the sequence converges to a value of approximately 1.46557123, the real root of the cubic equation x^3 - x^2 - 1 = 0. The exact value of the constant is shown in the image below.
- The nth term of the sequence can be computed directly with a Binet-like formula (as can all linear recurrence sequences.) C(n) = D*p^n + E*q^n + F*r^n, where p, q, and r are the roots of x^3 - x^2 - 1 = 0 and D, E, and F are coefficients chosen so that C(1) = C(2) = C(3) = 1.
- The parity of Narayana's cows numbers follows the pattern odd, odd, odd, even, odd, even, even,...
- The sum of the first n Narayana's cows numbers from C(1) to C(n) is equal to C(n+3) - 1. For example, if n = 10 and we sum the first eight Narayana's cows numbers we get 1 + 1 + 1 + 2 + 3 + 4 + 6 + 9 + 13 + 19 = 59, and 59 = 60 - 1.
- Imagine there is toad that can climb of a flight of stairs and it can hop a single step or three steps at a time; it can't hop exactly two steps at once or more than three steps at once. The number of ways the toad can hop n steps is C(n+1). For example, there are nine ways it can hop up seven steps. They are: 1111111, 11113, 11131, 11311, 13111, 31111, 133, 313, and 331.
Narayana's Cows Sequence in Nature and Art
Unlike the Fibonacci numbers and golden ratio that appear in often in botany and architecture, there are not any obvious examples of processes or structures that exhibit ratios with Narayana's cows numbers. However, American minimalist composer Tom Johnson, who bases many of his pieces on mathematical processes and patterns, wrote a piece based on Narayana's cows sequence.