IIT MS Question

Question

find T(n) = T(n-1)*T(n-2), given T(1) = a and T(2) = b

Comments

Devshree if you have understood the other solutions then use that to solve this problem because I cant. I will make you understand my solution tomorrow. By the way you can check that my solution is right by putting any number n.

---

@Kushagra Chatterje, For time being no issues.But it'll be appreciable if u explain tom.Thanks again brother. :)

---

Devshree I have explained it in the answer section below. I think you will understand my solution now. If you want to know how I am finding fn then please ask that as another question because if I show it here the answer would be long. If you dont undwrstand anything except that ask me.

Answer 1

NOTE 

1,1,2,3,5,..........  is a fibonacci series.

Name the above fibonacci series as fibonacci 1. 

Let us assume the n^th term of fibonacci 1 be f_n

then f_n = 1/√5 ( ( (1+√5)/2 )ⁿ   -   ( ( 1-√5)/2 )ⁿ ) (Consider this as a fact)

Now, come to our problem

Let us assume T(n) = a^k_n b^m_n  ........................................................... (1)

then T(n+1) = a^k_n+1 b^m_n+1...............................................(2)

Now, it is given in the question that T(n+2) = T(n) * T(n+1) 

=> T(n+2) = a^k_n b^m_n * a^k_n+1 b^m_n+1   from equations 1 & 2

=> T (n+2) = a^{(k_n + k_n+1)}  b^{(m_n + m_n+1)}

So, we are seeing that the power of 'a' in T(n+2) = summation of the powers of 'a' in T(n) and T(n+1)

Now, T (n+2) = a^k_n+2  b^m_n+2 

So, we get k_n+2 = k_n +k_n+1

Thus the powers of 'a' forms a fibonacci series.

Similarly we can say it for the powers of 'b'

here m_n+2 = m_n +m_n+1

Now, T(1) = a  so, k₁ = 1 and m₁ = 0

 Again T(2) = b so, k₂ = 0 and m₂ = 1

Thus the powers of 'a' forms the fibonacci series 1,0,1,1,2,......

name the above fibonacci series as fibonacci 2

If we look at the series fibonacci 1 and fibonacci 2 carefully we get that the n^th term of fibonacci 2 is equal to (n-2)^th term of fibonacci 1 for n>=3.

So, the terms of fibonacci 2 are

k₁ = 1  k₂ = 0 and k_n = f_n-2 for n>=3.

Similarly we get that the powers of 'b' forms the fibonacci series 0,1,1,2,.... name this series as Fibonacci 3

We get that n^th term of fibonacci 3 is equal to (n-1)^th term of Fibonacci 1 

so, the terms of Fibonacci 3 are

m₁ = 0, m₂=1 , m_n = f_n-1 for n>=3

So, our required solution T(n) = a^k_n b^m_n = a^f_n-2b^f_n-1 for n>=3.

Comments

@Kushagra Chatterjee,From where have u got squareroot of 5? Indeed a big Thanks for ur patience.:)

---

@Kushagra ,

 your final solution is T(n) = a^f_n-2b^f_n-1 , n>=3

Since according to your  f_n = 1/√5 ( ( (1+√5)/2 )ⁿ   -   ( ( 1-√5)/2 )ⁿ

if we put values of 'n' then f_n should be positive for n>=3

So, according to your solution , T(3) , T(4),..all should be started with 'a'

but here in question,

T(1) = a

T(2) = b

T(3) = ba

T(4) = bab

T(5) = babba

T(6) = babbabab

so on..

So, after T(2) , all strings are starting with 'b' if we consider * as concatenation in the question but your solution is giving strings which are starting with 'a'

Here , length of the strings are in fibonacci series.

ie. T(1) has length 1 

     T(2) has length 1

     T(3) has length 2

     T(4) has length 3

     T(5) has length 5

     T(6) has length 8

So, here length is in fibonacci sequence ie 1,1,2,3,5,8....

Now , recurrence equation for fibonacci series is a_n = a_n-1 + a_n-2

So, after solving,  it will give a_n = c₁(1 + sqrt(5))/2 + c₂(1-sqrt(5))/2

Now if we put base conditions here and find c₁ and c_{2 ...}

Now, how to solve further  ?

---

Ankit why are u keeping the strings intact as we keep in automata

Here we are given T(n) = T(n-1) * T(n-2)

Here, T(1) = a T(2) = b 

T(3) = a*b = ab

T(4) = T(3) * T(2) = ab * b = ab²

T(5) = T(4) * T(3) = ab² * ab = a²b³

T(6) = T(5) * T(4) = a²b³ * ab² = a³b⁵

........ and so on

Here we have to multiply a and b because the operator * (star) signifies it instead of concantenating it.

---

Devshree can u please post the question

How to compute the nth term of fibonacci series 1,1,2,3,5........

I will give you the answer there.

If you are having problem in anything except the computation of f_n please ask me.

and thank you too

It was nice discussing math with u

---

@kushagra, thanks.. Yes,it should be multiplication..I took it wrong..