IIT MS Question

Question

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

Comments

Consider the fibonacci series

1,1,2,3,5,8,.....

Let f_n denote the nth term of the above fibonacci series.

Consider another fibonacci series.

1,2,3,5,8,.....

Let k_n denote the nth term of the above fibonacci series.

So, the reqd result T(n) = a^(f_n-2) b^(k_n-2). for n>= 3.

Now, you can observe that k_n-2 = f_n-1  for n>=3.

So, T(n) = a^f_n-2 b^f_n-1.

Now, to find the nth term of the fibonacci series look at the following link.

http://www.askamathematician.com/2011/04/q-is-there-a-formula-to-find-the-nth-term-in-the-fibonacci-sequence/

---

@Kushagra Chatterjee,Consider visiting the solution in the link of stack overflow. 

Please can you use it to solve the question and share it as an answer?

https://stackoverflow.com/questions/26493945/how-to-solve-this-recurrence-relation-tn-tn-1-tn-2?noredirect=1&lq=1

---

Devshree in the solution given in the link of stackoverflow they are taking the log on both sides. Consider our problem

T (n) = T (n-1) * T (n-2)

=> log (T(n)) = log (T(n-1)) + log (T(n-2)) ..............................(1)

Now, let us assume log (T(n)) = K(n)

So, equation 1 becomes

K(n) = K(n-1) + K(n-2) ............................... (2)

Equation (2) is the recurrence relation of a fibonacci series. So, you have to solve the recurrrence relation of fibonacci series and then revert the log to get our actual answer.

If you don't know how to find  the nth term of fibonacci series using recurrence. Then go to this link

https://math.stackexchange.com/questions/545868/how-to-find-nth-term-in-a-fibonacci-series-or-sum-of-a-series-of-fibonacci-numbe

to find the generating function of fibonacci series

https://math.stackexchange.com/questions/338740/the-generating-function-for-the-fibonacci-numbers

read those links if you are having problem ask me.

---

@Kushagra Chatterjee,Thank you so much. :). Will definitely try.

---

@Kushagra Chatterjee,If I m not wrong then certainly in the explanation given in the link which you've mentioned, the series forms a GP brother?Isn't it?Am I right?Please correct me if I m wrong.

---

Devshree can u please write the first few terms of the series.

---

@Kushagra Chatterjee,brb. Will share it soon. Yeah. :) :D

---

Devshree sorry to say  can I stick to my original solution? because the calculations are becoming very tedious . Tell me if there is any problem in my initial solution.

---

@Kushagra Chatterjee, ur ans alone I haven't understood brother. Could you please elaborate it?

---

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

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..