Set Theory Consider the alphabet a b and operation suba ab

(Set Theory)

Consider the alphabet {a, b}, and operation sub(a) = ab and sub(b) = a. Given any string w_1 w_2 W_k, let next (w_1 w_2 ... w_k) = sub (w_1)sub(w_2) sub ... (w_k). Beginning with the string a, we can iteratively apply next to make strings which involve a\'s and b\'s and compute the length of the string at each iteration. For instance, the first iteration gives us a of length 1, the second iteration gives us ab of length 2, the third gives aba of length 3, etc... Show that the nth iteration gives us a string of length Fn, the nth Fibonacci number

Solution

1.....................a                -->t₁ = 1
2.....................ab              -->t₂ = 2
3.....................aba            -->t₃ = 3
4.....................abaab        -->t₄ = 5
5.....................abaababa   -->t₅ = 8

From the above series we can say t₁, t₂, t₃, t₄, t₅ are in fibo. series

we can also infer that

a_n = Number of a in n+1 itteration = number of a + number of b = a_n + b_n

b_n = Number of b in n+1 itteration = number of a = a_n

therefore
a_n+1 = a_n + b_n      //a_n is number of a in n^th iteration
b_n+1 = a_n              //b_n is number of b in n^th iteration

a_n+2 = a_n+1 + b_n+1 = a_n + b_n + a_n << This is number of charecters in n+1 iteration (T_n+1)
b_n+2 = a_n+1 = a_n + b_n <<This is number of charecters in n iteration(T_n)

as we can see

Therefore we proved that T_n = F_n