in Algorithms retagged by
857 views
0 votes
0 votes
find T(n) = T(n-1)*T(n-2), given T(1) = a and T(2) = b
in Algorithms retagged by
by
857 views

4 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.
0
0
@Kushagra Chatterje, For time being no issues.But it'll be appreciable if u explain tom.Thanks again brother. :)
0
0
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.
0
0

1 Answer

2 votes
2 votes

NOTE 

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

Name the above fibonacci series as fibonacci 1. 

Let us assume the nth term of fibonacci 1 be fn

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

Now, come to our problem

Let us assume T(n) = akn bm........................................................... (1)

then T(n+1) = akn+1 bmn+1...............................................(2)

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

=> T(n+2) = akn bmn * akn+1 bmn+1   from equations 1 & 2

=> T (n+2) = a(kn + kn+1)  b(mn + mn+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) = akn+2  bmn+2 

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

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

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

here mn+2 = mn +mn+1

Now, T(1) = a  so, k1 = 1 and m1 = 0

 Again T(2) = b so, k2 = 0 and m2 = 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 nth term of fibonacci 2 is equal to (n-2)th term of fibonacci 1 for n>=3.

So, the terms of fibonacci 2 are

k1 = 1  k2 = 0 and kn = fn-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 nth term of fibonacci 3 is equal to (n-1)th term of Fibonacci 1 

so, the terms of Fibonacci 3 are

m1 = 0, m2=1 , mn = fn-1 for n>=3

So, our required solution T(n) = akn bmn = afn-2bfn-1 for n>=3.

edited by

4 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 = ab2

T(5) = T(4) * T(3) = ab2 * ab = a2b3

T(6) = T(5) * T(4) = a2b3 * ab2 = a3b5

........ and so on

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

1
1
edited by

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 fn please ask me.

and thank you too

It was nice discussing math with u

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

Related questions