FIBONACCI’S NUMBERS AND RECURSION
1. In 1202, Leonardo Fibonacci asked the question: "How many pairs of rabbits can be produced from a single pair in a year's time?" Assume that each pair produces a new pair of offspring every month, each new pair becomes fertile at the age of one month, and the rabbits never die. What is the answer to Fibonacci's problem?
Answer
After one month, there will be 2 pairs of rabbits; after 2 months, there will be 3 pairs of rabbits. On the 3rd month, both the original pair and the pair during the first month will give birth to new pair and there will be 5 in all; and so on. This is the basis for the Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, 21, 34,…. We can see that on the 7th month, there will be 34 pairs of rabbits in all.
In general, F0 = F1 = 1, Fn = Fn-1 + Fn-2 for n > = 2.
To find the number of pairs of rabbits at a month n is to find the value of Fn+1.
Consider the recursion relation Fn = aFn-1 + bFn-2. If b = 0 then Fn = aFn-1 = a²Fn-2…= aⁿF0.
If a = 0, then F2 = bF0, F4 = bF2 = b²F0..,so F2n = bⁿF0
Likewise, F3 = bF1, F5 = bF3 = b²F1…, so F2n+1 = bⁿF1
From the above special cases, we hope that there is a solution for Fn = crⁿ where rⁿ = arⁿ-¹ + brⁿ-²
Dividing by rⁿ-2, gives r² - ar – b = 0
In other words if Fn = crⁿ for all n, then r must be a solution x = r of the quadratic equation x² - ax – b = 0
Going back to the Fibonacci sequence, F0 = 0, F1 = 1, and Fn = Fn-1 + Fn-2 for n >= 2. Here a = b = 1 and the quadratic equation becomes x² - x – 1 = 0 with solutions r = (1+√5)/2 and s = (1-√5)/2. The sequence Fn can be written as Fn = crⁿ. The above equation has 2 solution r and s, then Fn can be written as
Fn = c1rⁿ + c2sⁿ = c1[(1+√5)/2]ⁿ + c2 [(1-√5)/2]ⁿ
For n = 0, and n = 1, 1 = c1 + c2, and 1 = c1r + c2s. Replacing for r and s and solving the equations we get:
Fn = (1/√5)[ ((1+√5)/2)ⁿ+¹ – ((1-√5)/2)ⁿ+¹ ]
The number (1+√5)/2 is usually called the golden constant and it approximates 1.6 and has many applications. Artists best rectangle is the one with length and width ratio of 1.6.
2. What is the number of words of length 3 that you can make from the set of letters ∑ = {a, b} and do not have consecutive a's i.e. do not contain the string aa?
Answer
The words of length 3 that can be made from the set ∑ are ∑³ = {aaa, aab, baa, aba, bba, abb, bbb, bab} and they count 2³ = 8. Our set excludes those with consecutive a's and it is {aba, bba, abb, bbb, bab} with count of 5. Now this is simple exercise and it is a forword for finding the number Sn of words of length n that do not have consecutive a's. Let Bn be the set of words in ∑n having no consecutive a's. Then B0 = {€}, B1 = ∑ = {a, b}, and B2 = ∑²- aa = {ab, ba, bb}. Then S0 = 1, S1 = 2, S2 = 4-1 = 3. We can get a recursion formula for Sn in terms of Sn-1 and Sn-2 for n>=2.
If a word in Bn ends with b then it can be preceded by any word in Bn-1. The number of words in Bn-1 is Sn-1, so Sn-1 words in Bn ends in b. If a word in Bn ends in a, then its last two letters must be "ba" and this string can be preceded by any word from the set Bn-2 which counts Sn-2. Hence, the number of words Sn in set Bn can be written as Sn = Sn-1+Sn-2 for n >=2. In the above question, S3 = S1 + S2 = 2 + 3 = 5. This is a similar recursion relation to that of the Fibonacci sequence where Fn = Fn-1 + Fn-2 and F1 = 1 while S1 = 2. Fibonacci sequence is 1,1,2,3,5,8,13,...
The number of words of length n with consecutive a's in the set ∑n will be (2²- Sn) where the total number of words in ∑n is 2².
Using a computer program / algorithm we can apply this recursion relation and find Sn.
3. What is the number of words of length 2 that you can make from the set of letters ∑ = {a, b, c} with even number of a's?
This set B2 is {aa, bb, bc, cb, cc} and counts 5. The whole set ∑² with words of length 2 is {aa, ab, ac, ba, bb, bc, ca, cb, cc} and counts to 3² = 9.
Let's now find sn the number of words of length n and with even number of a's i.e. find the relation in terms of n. Let Bn be this set. Bn is a subset of ∑n the set of all the words with length n. B0 = { }, B1 = {b, c}, B2 = as above. So, S0 = 1, S2 = 2, S3 = 5 and so on. Now, we will try to find Sn in terms of Sn-1 and Sn-2 as a recursion relation. This is simple. If a word in Bn ends in b or c, then it can be preceded with any word in Bn-1 because in B n-1, all the words are assumed to be with even number of a's, so the number of words ending in b or c in Bn is Sn-1 + Sn-1 = 2Sn-1 where S n-1 is the number of words in B n-1.
If a word in Bn is ending with a, then it must be preceded by a word in ∑n-1 with odd number of a's. Now, ∑n-1 has 3ⁿ -¹ words, and Sn-1 of these have even a's. So, the number of words with odd a's in ∑n-1 is (3ⁿ -¹ - Sn-1).
Adding up, Sn = 2Sn-1 + (3ⁿ -¹ - Sn-1) = 3ⁿ -¹ + Sn-1
As an example, S3 = S2 + 3² = 5 + 9 = 14.
Sn = 3ⁿ -¹ + 3ⁿ -² +....+ 3º+ S0 = S0 + (3ⁿ - 1)/(3 – 1).
S0 = 1, so [Sn = (3ⁿ + 1) / 2]