New Batches at TathaGat Delhi & Noida!
Fibonacci Series- Counting and Recursion
by TG Team - Thursday, 8 April 2010, 01:49 PM
 

Fibonacci Series- Counting and RecursionA few weeks ago, I was having a telephonic conversation with two of our past students currently studying in IIM-A- Avijit and Dhawal. The curious thing about this was that Avijit was our online student whereas Dhawal was our classroom student. And I remembered how we used to tell Dhawal and his classmates in TathaGat that "there is a guy from Orissa who is performing better than you guys in CopyCATs." As I think of it, it is strange that we are still so close to our students. There is Rishu Batra, a sweet and lovable TGite, Jatin Bhagat who finally cracked CAT after three years, the serious Chinmay Kolharkar at Great Lakes, Himanshu Tyagi who left his job despite our warnings and didn't do well, cool dude Maneesh Dhooper who has been completely unlucky in his last two CATs but converted XL this year, intelligent Shruti who would choke during every test but finally got an IIM K call, and Saurabh Chhajer of this year who scored the highest in quant in Chhota CopyCAT but disappointed us because we know his calibre. These are some of the ones I can think of right now but I wonder how many evenings we have passed discussing "ye student quant ya verbal mein kaisa hai" or "is student ko thoda aur hardwork chahhiye" or that "ye student intelligent hai but hardwork nahin karta" and all that stuff. Year by year, there is a growing feeling among us- TG is a family. And although we are known as hard taskmasters and what not, we do love all our students. We would like to keep it that way.

Today's article is the culmination of discussions between Kamal and me about a particular type of problems. It is strange how when you learn a new funda and go out to find problems based on that, you slowly start uncovering so many different types of problems which can be solved through that funda. Or maybe that you solved a problem but then started looking for a better solution and suddenly remembered a long-forgotten funda, and once you started applying that funda you discovered many more such problems where you can apply it. Our discussions usually make these kinds of discoveries. One of them is here. Enjoy!- Total Gadha

fibonacci introduction fibonacci continued fibonacci properties

 

Share or Tweet This!


Bookmark and Share
Books To Refer:

Fibonacci and Lucas Numbers with Applications




You Might Also Like:

CAT CBT Club: TotalGadha's Exclusive Membership Section
TathaGat: TotalGadha's CAT Classroom Coaching
CAT Quant Lessons: Quant Lessons for MBA Preparation
CAT Verbal Lessons: Verbal Lessons for MBA Preparation
CAT Quant/DI Forum: Ask doubts related to Quant & DI
CAT Verbal Forum: Ask doubts related to Verbal
Re: Fibonacci Series- Counting and Recursion
by Dev Raj - Friday, 9 April 2010, 05:16 AM
  TG sir,

Thank you so much for the above article...Number systems haunt me and TG has become my way of exorcism....
Pls allow me to chew on this concept for a while and bang my head against it and I will be back with doubts...

I would like to say a little about the writeup just before the number theory takes over. I would like to extend my heartfelt gratitude towards You and Dagny ma'm, especially towards Dagny ma'm because you two have helped me a lot in changing my perspective towards CAT....Though I am just into my second week of preparation and only the first week with TG, the way I used to approach studies has changed gradually and steadily if not the scores..(i believe they will change for better with time too..).

I had rather you did this job for a thousand years to come to help millions more like me.....

It boosts my morale to have your presence with me during my journey towards CAT and I am becoming all the more determined with time  to prove myself as an ardent student of yours and get my name included in the above list of students that you still remember and be in touch with.

Pls continue with the good work and look out for me in your top scorers in the near future.

Regards,
Dev

Re: Fibonacci Series- Counting and Recursion
by jaya rughani - Saturday, 10 April 2010, 01:55 PM
  Great ! the explaination of derrangement is perfect
Re: Fibonacci Series- Counting and Recursion
by Total Gadha - Saturday, 10 April 2010, 02:27 PM
  Hi Dev,

Welcome to TG. smile

Total Gadha
Fibonacci Series- Counting and Recursion
by TG Team - Saturday, 10 April 2010, 02:45 PM
 

Thanks Jaya smile

Your next task is to solve the questions asked in the article.

Re: Fibonacci Series- Counting and Recursion
by sharad mishra - Saturday, 10 April 2010, 02:47 PM
  hi
this article is very interesting . i just struck at question number 7(question on jar liquid transfer).plz give us the solution .
Re: Fibonacci Series- Counting and Recursion
by TG Team - Sunday, 11 April 2010, 02:18 PM
 

Sharad smile

Just write down the composition of jars after every transfer.

Re: Fibonacci Series- Counting and Recursion
by sharad mishra - Monday, 12 April 2010, 01:05 AM
  tg sir
still not able to apply the concept of fibonacci at question 6 and 7. plz give me a proper guideline.
thanx (in advance)
with regards
Re: Fibonacci Series- Counting and Recursion
by vinay mudgil - Monday, 12 April 2010, 04:14 PM
  Greetings,

To be honest with myself, I must read this article again in order to completely grasp the concept... but until now here are my answers for first five questions...

(1) data insufficient
(2) 2408280
(3) 9169922
(4) 246
(5) 683

Please let me know if they are correct [i am not very confident this time].

Thank you !!!
Re: Fibonacci Series- Counting and Recursion
by abhishek kundan - Monday, 12 April 2010, 05:52 PM
  i think the formula given for summation of fibonacci series is wrong..
it should be
 Sn= Fn+2 - F2

e.g: 2, 3, 5, 8 , 13, 21....

suppose we have to find S4 i.e 2+3+5+8=18
by your formula (
Sn= Fn+1 - F2)  : = 13-3=10 which is wrong ans.
by above mentioned formula its coming right..i.e. Sn= 21-3=18 which is the ans.
Re: Fibonacci Series- Counting and Recursion
by Total Gadha - Monday, 12 April 2010, 06:18 PM
  Hi Abhishek,

You are right, the derivation above was giving Sn - 1 and not Sn. Thanks for pointing out. smile

Total Gadha
Fibonacci Series- Counting and Recursion
by TG Team - Tuesday, 13 April 2010, 06:16 PM
 

Sharad smile

Though you have asked this to TG but I need to intervene because I have wrote the article and the questions.

Regarding question 6 and 7 it is not necessary to use fiboacci but you can find some pattern, sequence or recursion. In the remaining first five questions also you must not have used fibonacci in every question, I hope. smile

 

 

Vinay smile

Data is sufficient in all the questions. And I must agree that you need to read the complete article two-three times to grasp the concept and ideology completely.

One more thing, it would be proper to comment on your answers once you are confident about them. So please re-read the article , develop confidence and solve the questions. I'm sure you'll be able to solve all seven questions pretty easily. smile

 

Abhishek smile

Thanks for reading my article with utmost concentration. It was a typo and I have corrected it in my original manuscript also.

Anyways, tell me did you find the article useful or not? smile  

Re: Fibonacci Series- Counting and Recursion
by kuntal chattrejee - Tuesday, 13 April 2010, 10:25 PM
 

After having such solid discussion on FS,i would like to tell something about FS:

1st : 1/998999 = .000001001002003005008013021034055089.....goes on

2nd: 1/99989999= .00000001000100020003000500080013002100340055...goes on

if we observe the numbers padded inside 0...is it not the known fibonacci series?

this pattern is more or less true if we proceed more like 1/( 'n times 9'8'n+1 times 9')

smile....may not help that much..but i wrote it for the pattern.

Re: Fibonacci Series- Counting and Recursion
by TG Team - Thursday, 15 April 2010, 02:56 PM
 

Thanks Kuntal smile for the pattern you provided.

Actually it seem that it is giving the Fibonacci sequence as its first few terms are following the same pattern i.e. an = an-1 + an-2 but not later as they are getting merged.

  • 1/89 = 0.0112359550561797752808988764044943820224719101123595505617...
  • 1/9899 = 0.0001010203050813213455904636832003232649762602283058894837...
  • 1/998999 = 1.0010020030050080130210340550891442333776109885995881... x 10-6

Now see some more magic; what do you obseve in the following expansions:

  • 1/9898 = 0.0001010305112143867447969286724590826429581733683572438876...
  • 1/998998 = 1.0010030050110210430851713416843677364719448887785561... x 10-6

First few terms after decimal (in packets of 2 and 3 respectively) are following the pattern an = an-1 + 2an-2 , And here

  • 1/9897 = 0.0001010407194099221986460543599070425381428715772456299888...
  • 1/998997 = 1.0010040070190400972175091616891742417644897832526023... x 10-6

first few terms after decimal (in packets of 2 and 3 respectively) are following the pattern an = an-1 + 3an-2

This magic can easily be understood by Binomial Expansion because

1/89 = 1/(100 - 11) = (100 - 11)-1 = 100-1(1 - 0.11)-1

Similarly 1/9899 = 10000-1(1 - 0.0101)-1 and so on.

Remember (1 - x)-1 = 1 + x + x2 + ... smile

Re: Fibonacci Series- Counting and Recursion
by Vikas KUmar - Thursday, 15 April 2010, 03:00 PM
 

Awesome article.....

I am Vikas. Software Engineer in Nucleus Software Noida.

I have been an ardent follower of TG for the last one year. Ihave already purchased your online resources.

I wanna join your online course.

Kindly suggest how to do the same.

 

Regards,

Vikas

Re: Fibonacci Series- Counting and Recursion
by jaya rughani - Friday, 16 April 2010, 01:02 PM
  For Q.1 the ans. is 194.
Re: Fibonacci Series- Counting and Recursion
by TG Team - Friday, 16 April 2010, 05:35 PM
 

Hi Vikas smile

It's nice to see that you liked the article. Regarding our online course you can join our CBT-Club. For details about that look in the upper left corner of main page.

Re: Fibonacci Series- Counting and Recursion
by TG Team - Friday, 16 April 2010, 05:36 PM
 

Hi Jaya smile

Your answer is indeed correct. Little explanation will be more than welcome. smile

Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Thursday, 22 April 2010, 06:30 PM
  Dear sir,
            I have a certain doubt in the 5th example(regarding the smallest value of n). Why do the lengths of the 10 line segments need to form a Fibonacci sequence ? Is it necessary? If we take a fibonacci sequence represented by the equation fn+1 = fn + fn-1, then sum of the sides of the triangle equal in length to fn and fn-1 respectively would give a resultant length equal to fn+1.But for the triangle to exist fn+1 should be greater than (fn + fn-1) and not equal.

Subhash
Re: Fibonacci Series- Counting and Recursion
by TG Team - Thursday, 22 April 2010, 06:33 PM
 

Hi Subhashsmile

Please go through the explanation again. I think I've written enough words there. Try to make the sequence of side lengths in increasing order on your own and observe the pattern you'd be writing. smile

Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Thursday, 22 April 2010, 07:50 PM
  I am sorry sir.Actually, i skipped a few words and misinterpreted your  question.I apologize again.

Regards,
Subhash
Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Thursday, 22 April 2010, 10:12 PM
  Dear sir,
           I shall be posting my answers to the questions one at a time.
Solution to Qn1:
a7 = 120
    = a5 + a6
    = a5 + a4 + a5
    = 2a5 + a4
    = 2(a3 + a4) + a4
    = 2a3 + 3a4
    = 2a3 + 3(a2 + a3)
    = 5a3 + 3a2
    = 5(a1 + a2) + 3a2
    = 5a1 + 8a2

=>5a1 + 8a2 = 120
Using Extended Euclidean Algorithm,
we can find that the smallest positive integral values satisfying this equation are a1 = 8 and a2 = 10

Now,
a8 = a6 + a7
    = a6 + (a5 + a6)
    = 2a6 + a5
    = 2(a4 + a5) + a5
    = 2a4 + 3a5
    = 2a4 + 3(a3 + a4)
    = 5a4 + 3a3
    = 5(a2 + a3) + 3a3
    = 5a2 + 8a3
    = 5a2 + 8(a1 + a2)
    = 8a1 + 13a2
    = 8*8 + 13*10
    = 64 + 130
    = 194

Kindly correct me if i am wrong somewhere.

Regards,
Subhash


Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Thursday, 22 April 2010, 10:21 PM
  a8 = 194 is the least possible value for a8. It could have other values too depending on the values of a1 and a2. Regards, Subhash
Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Thursday, 22 April 2010, 11:35 PM
  Solution to Qn3:
Sn = fn+2 - f2
    = (fn+1 + fn) - f2
    = (fn + fn-1 + fn) - 11
    = (2fn + fn-1) - 11
    = (2*2995 + 1851) - 11
    = 7830

Regards,
Subhash

 
Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Thursday, 22 April 2010, 11:54 PM
  Solution to Qn2:

Sn = F1^2 + Fn*Fn+1 - F1*F2
    = 2^2 + 1220*(754 + 1220) - 2*4
    = 4 + 1220*1974 - 8
    = 4 + 2408280 - 8
    = 2408276

Regards,
Subhash
Re: Fibonacci Series- Counting and Recursion
by avijit mohapatra - Friday, 23 April 2010, 09:44 AM
 

Hello Kamal sir and TG sir

I still miss those CAT preparation days. I and Dhawal discuss that preparing for CAT, solving new types of question and giving numerous tests of varied pattern and difficulty level was awesome fun. I enjoyed every bit of preparation and would suggest all the CAT aspirants to enjoy the process to the utmost.

Presently I am interning at Mumbai and I am so happy that TG is accessible from my office where most of the social netorking and log-in sites are blocked.

Have fun and Rock on

 

Re: Fibonacci Series- Counting and Recursion
by Total Gadha - Friday, 23 April 2010, 12:20 PM
  Hi Avijit,

That is true. I think I had more fun during my CAT preparation than during my JEE preparaition. Felt like an adventure. smile

By the way, you blog at TG Town needs your attention.  Do write something. Writing is a satisfying love for life. Once you get into it, life is never the same again. smile

Total Gadha
Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Friday, 23 April 2010, 12:45 PM
  Solution to Qn4:
Let's apply the reverse count method.

Let us assume that there are fn+1 ways for filling in the digits of an n-digit number.

When 1st digit = 1 remaining n digits can be filled in fn ways.
When 1st digit = 2 & 2nd digit =1 remaining n-1 digits can be filled in fn-1 ways.
When 1st digit = 2 & 2nd digit = 2 3rd digit has to be = 2.So the remaining n-2 digits can be filled in fn-2 ways.

Therefore,
 fn+1 = fn + fn-1 + fn-2 .....................(1)

Now,
f1 = 2, f2 = 4(as the 1st two digits could be 11 or 12 or 21 or 22)
f3 = 7(as the 1st three digits could be either of 111,112,121,122,211,212,222  but not 221).
Therefore,
 f4 = 7 + 4 + 2 = 13, f5 = 13 + 7 + 4 = 24, f6 = 24 + 13 + 7 = 44 ...(2)
Putting n + 1 = 10 in (1) we get,
f10 = f9 + f8 + f7
      = 7f6 + 6f5 + 4f4 (On simplification)
      = 7*44 + 6*24 + 4*13
      = 308 + 144 + 52
      = 504

Kindly correct me if i am wrong.

Regards,
Subhash
Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Friday, 23 April 2010, 01:26 PM
  Dear sir,
           Here's the solution to Qn5:

Let us assume that there are fn+1 ways for tiling a 2 x (n + 1) area.

Now,
       the beginning 2 x 1 area can be tiled in only one way, which is, by using a single 2 x 1 tile.
Hence, f1 = 1.
The remaining 2 x n area can be tiled in fn ways.

Again,
        the beginning 2 x 2 area can be tiled in two ways.(which are, by laying two 2 x 1 tiles side by side or by stacking one 2 x 1 tile on top of another).
Hence, f2 = 2.
The remaining 2 x (n-1) area can be tiled in fn-1 ways.

Again,
        the beginning 2x3 area can be tiled in four ways( either by laying three 2 x 1 tiles side by side, or by stacking one 2 x 1 tile on top of another and then laying a 2 x 1 tile at the end vertically, or by laying a 2 x 1 tile vertically and then laying two 2 x 1 tiles horizontally one on top of the other, or by using two L-shaped tiles in such a way that they lock together.)

Hence, f3 = 4.
The remaining 2 x(n - 2) area can be tiled in fn-2 ways.

Therefore,
fn+1 = fn + fn-1 + fn-2 ......(1)

Using n + 1 = 10 => n = 9,we get

f10 = f9 + f8 + f7...(2)
Also
f4 = f3 + f2 + f1...(using 1)
    = 4 + 2 + 1
    = 7
f5 = f4 + f3 + f2
    = 7 + 4 + 2
    = 13
f6 = f5 + f4 + f3
    = 13 + 7 + 4
    = 24
f7 = 24 + 13 + 7
    = 44
f8 = f7 + f6 + f5
    = 44 + 24 + 13
    = 81
f9 = f8 + f7 + f6
    = 81 + 44 + 24
    = 149

f10 = 149 + 81 + 44
      = 274

Therefore, there are 274 ways to tile the area.
Kindly correct me if i am wrong.

Regards,
Subhash
   
Re: Fibonacci Series- Counting and Recursion
by TG Team - Friday, 23 April 2010, 03:14 PM
 

Subhash smile

Regarding first question it is given that a1, a2, ... is an increasing sequence of positive integers, so the values you have calculated for a1 and a2 are the only possible values. In all other cases; either a1 > a2 or both of a1, a2 will not remain positive integers. Thus correct answer for 1st question is 194. smile

Your answers to second and third questions are also perfectly right. smile

Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Friday, 23 April 2010, 03:42 PM
  Dear sir,
           I think the following should be the solution to Qn7.

Solution to Qn7:
Assumption: Shaking hands with left-hand & shaking hands with right-hand are equivalent.
Let us assume that fn+1 is the number of ways in which n+1 people seated around the table could shake hands with each other.

One person alone cannot shake hands with another. Therefore f1 = 0.
The remaining n people can shake hands with each other in fn ways.

Now,
       two people can shake hands with each other in only one way(due to the assumption).Therefore, f2 = 1.The remaining n-1 people can shake hands with each other in fn-1 ways.

Similarly,
             three people can shake hands with each other in three ways.
Therefore, f3 = 3.The remaining n-2 people can shake hands with each other in fn-2 ways.

Similarly,
             four people can shake hands with each other in 4C2 = 6 ways.Therefore, f4 = 6. The remaining n-3 people can shake hands with each other in fn-3 ways.

Similarly,
             5 people can shake hands with each other in 5C2 = 10 ways.Therefore, f5 = 10. The remaining n-4 people can shake hands with each other in fn-4 ways.

Therefore,
               fn+1 = fn + fn-1 + fn-2 + fn-3 + fn-4    .........(1)

Also,
      f1 = 0,f2 = 1,f3 = 3,f4 = 6, f5 = 10 ......(2)

Putting n+1 = 12 in (1), we get,
f12 = f11 + f10 + f9 + f8 + f7 ......(3)

Using, (1) and (2), we get,
 f6 = f5 + f4 + f3 + f2 + f1
     = 10 + 6 + 3 + 1 + 0
     = 20
 f7 = 20 + 10 + 6 + 3 + 1
     = 40
 f8 = 40 + 20 + 10 + 6 + 3
     = 79
 f9 = 79 + 40 + 20 + 10 + 6
     = 155
 f10 = 155 + 79 + 40 + 20 + 10
       = 155 + 149
       = 304
  f11 = 304 +155 + 79 + 40 + 20
        = 304 + 294
        = 598
  Therefore,
                 f12 = f11 + f10 + f9 + f8 + f7
                      = 598 + 304 + 155 + 79 + 40
                      = 1176

Therefore, the number of ways in which hands could be shaken = 1176.

Kindly correct me if i am wrong somewhere.

Regards,
Subhash
Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Friday, 23 April 2010, 11:29 PM
  Dear sir,
           I could not apply fibonacci series in solving Qn6. But i have solved it using simple A.P..

Solution to Qn6:

                          Urn 1                             |                       Urn2
Initial:                    1                                |                         0
1st stage:               1/2                             |                         1/2
2nd stage:          1/2 + (1/3)*(1/2) = 2/3      |                   (2/3)*(1/2) = 1/3
3rd stage:           (3/4)*(2/3) = 1/2              |            1/3 + (1/4)*(2/3) = 1/2
4th stage:        1/2 + (1/5)*(1/2) = 3/5         |            (4/5)*(1/2) = 2/5
5th stage:        (5/6)*(3/5) = 1/2                 |            2/5 + (1/6)*(3/5) = 1/2
6th stage:        1/2 + (1/7)*(1/2) = 4/7         |                (6/7)*(1/2) = 3/7
 

As we can see, that if we leave out the 1/2's then the for the rest of the values for each stage for urn 1, there is a pattern:

1,2/3,3/5,4/7....

The numerators of the above fractions form an A.P. with 1st term = 1 and common difference = 1.

The denominators of the above fractions form another A.P. with 1st term = 1 and common difference = 2 
 
So, for finding the value of the fraction for urn 1 for the 2010th stage, we have to observe that in an odd-numbered stage, the value of the fraction is 1/2. So, we have to consider only the even stages.

Therefore, n = 2010/2 = 1005

Therefore, 1005th term for the first A.P.,
 t1005 = 1 + (1005 - 1)*1
          = 1 + 1004
          = 1005

Similarly,1005th term for the second A.P.,
t'1005 = 1 + (1005 - 1)*2
         = 1 + 1004*2
         = 1 + 2008
         = 2009

Therefore, the required fraction of the initial amount present in urn 1 in the 2010th stage = 1005/2009 Answer.

Kindly correct me if i am wrong.
Regards,
Subhash
            
Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Friday, 23 April 2010, 11:34 PM
  Dear sir,
           Kindly do let me know how to solve Qn6 using Fibonacci series.

Regards,
Subhash
Re: Fibonacci Series- Counting and Recursion
by TG Team - Sunday, 25 April 2010, 12:42 PM
 

Subhashsmile

Question 4:

In your terms, let fn+1 be the number of ways of forming n digit number with digits 1 and 2 only such that 221 doesn't occur at any place.

  • Now if first digit is 1, then remaingn digits can be filled in fn ways.
  • If first digit is 2, then there are two cases-
  • If first two digits are 21, then there are fn-1 ways, but
  • If first two digits are 22, then there is only 1 way. Remember that one way is to put only 2s in this sequence. We can never put any 1 here.

So fn+1 = fn + fn-1 + 1

Now calculate. smile

 

 

Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Sunday, 25 April 2010, 05:39 PM
  Dear sir,
           Thank you for pointing out my mistake.
Therefore, the proper solution to Qn4 would be:

f1=2,f2=4,f3=7

fn+1 = fn + fn-1 + 1

Taking n+1 = 10, we get,

f10 = f9 +f8 + 1
      =(f8 + f7 + 1) + f8 + 1
      = 2f8 + f7 + 2
      = 2(f7 + f6 + 1) + f7 + 2
      = 3f7 + 2f6 + 4
      = 3(f6 + f5 + 1) + 2f6 + 4
      = 5f6 + 3f5 + 7
      = 5(f5 + f4 + 1) + 3f5 + 7
      = 8f5 + 5f4 + 12
      = 8(f4 + f3 + 1) + 5f4 + 12
      = 13f4 + 8f3 + 20
      = 13(f3 + f2 + 1) + 8f3 + 20
      = 21f3 + 13f2 + 33
      = 21*7 + 13*4 + 33
      = 147 + 52 + 33
      = 232 Answer.

Regards,
Subhash
      =
Re: Fibonacci Series- Counting and Recursion
by TG Team - Sunday, 25 April 2010, 07:56 PM
 

Yes Subhash smile

You are right this time. Now recheck your answer for question number 5 also.

Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Monday, 26 April 2010, 03:41 AM
  Dear sir,
            I think i have caught my mistake in Qn 5. The value of f3 should be equal to 5 and not 4.

Solution for Qn 5:

Let us suppose a 2 * (n+1) area could be laid by using 2*1 and L-shaped tiles in fn+1 ways.

Now,
       a 2*1 area could be laid in only one way, which is,by using a single 2*1 tile.
Therefore, f1 = 1.The remaining 2*n area can be laid in fn ways.

Again,
       a 2*2 area could be laid in two ways, which are by laying two 2*1 tiles side-by-side and by laying two 2*1 tiles stacked one on top of the other.
Therefore, f2 = 2.The remaining 2*(n-1) area can be laid in fn-1 ways.

Again,
        a 2*3 area could be laid in 5 ways. It could be laid either by laying three 2*1 tiles side-by-side, or by laying two 2*1 tiles one on top of the other and then laying a 2*1 tile vertically, or by first laying a single 2*1 tile vertically and then laying two 2*1 tiles one on top of the other.It could also be laid either by using an L-shaped tile vertically straight and then using another L-shaped tile inverted so that the two tiles lock into each other
or by first using an inverted L-shaped tile and then a vertically straight L-shaped tile.
Therefore, f3=5.The remaining 2*(n-2) area can be laid in fn-2 ways.

fn+1 = fn + fn-1 + fn-2 ..........(1)

Taking, n + 1 = 10, we get,

f10 = f9 + f8 + f7

Also, f1 = 1,f2 = 2 & f3 = 5.

Therefore,
f4 = 5 + 2 + 1 = 8
f5 = 8 + 5 + 2 = 15
f6 = 15 + 8 + 5 = 28
f7 = 28 + 15 + 8 = 51
f8 = 51 + 28 + 15 = 94
f9 = 94 + 51 + 28 = 173
f10 = 173 + 94 + 51 = 318 Answer

Regards,
Subhash
Re: Fibonacci Series- Counting and Recursion
by TG Team - Monday, 26 April 2010, 01:31 PM
 

Subhash smile

Please go through the explanation of similar question in article and try to formulate the recursion properly.  

Re: Fibonacci Series- Counting and Recursion
by avijit mohapatra - Monday, 26 April 2010, 04:10 PM
 

Hello TG sir

                I got busy during the weekend with lots of work at office. Was working till 1 in the night even during the weekend. I will get my blog up and running soon. I am planning to join back the verbal forums; it was real fun.

Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Monday, 26 April 2010, 04:42 PM
  Dear sir,
            I think the following should be the solution to Qn 5.
Let us suppose that there are fn ways to tile a 2 * n area.

This includes the first case where the first tile is a 2*1 tile vertically upright(kindly see Case1 in the attachment).
Therefore, f1=1. The remaining 2*(n-1) area can be tiled in fn-1 ways.

Also included is the case when the the beginning 2*2 area is tiled using two 2*1 tiles stacked one on top of the other(kindly see Case2 in the attachment).
Therefore, f2 = 1. The remaining 2*(n-2) area can be tiled in fn-2 ways.

Also included is the case when the beginning 2*3 area is tiled using two L-shaped tiles, the first of which is upright and the second inverted, so that they lock together.Again, the first tile could be inverted and the second could be upright(kindly see cases 3 & 4 in the attachment).
Therefore, f3 = 2.The remaining 2*(n-3) area could be tiled in 2*fn-3 ways.

Again, the first 2*4 area could be tiled using two L-shaped tiles and a 2*1 tile such that the L-shaped tiles face each other and the 2*1 tile is held between them.(Kindly see cases 5 & 6 in the attachment).
Therefore, f4 = 2.The remaining 2*(n-4) area could be tiled in 2*fn-4 ways.

Therefore,
               fn = fn-1 + fn-2 + 2*fn-3 + 2*fn-4 .......(1)

Aslo,
      f1 = 1,f2 = 1,f3 = 2, f4 = 2.....(2)
     
      f5 = f4 + f3 + 2*f2 + 2*f1
          = 2 + 2 + 2*1 + 2*1
          = 4 + 4
          = 8
      f6 = f5 + f4 + 2*(f3 + f2)
          = 8 + 2 + 2*(2+ 1)
          = 10 + 2*3
          = 10 + 6
          = 16
      f7 = f6 + f5 + 2*(f4 + f3)
          = 16 + 8 + 2*(2 + 2)
          = 24 + 8
          = 32
      f8 = f7 + f6 + 2*(f5 + f4)
          = 32 + 16 + 2*(8 + 2)
          = 48 + 2*10
          = 48 + 20
          = 68
      f9 = f8 + f7 + 2*(f6 + f5)
          = 68 + 32 + 2*(16 + 8)
          = 68 + 32 + 2*24
          = 68 + 32 + 48
          = 148
     f10 = f9 + f8 + 2*(f7 + f6)
          = 148 + 68 + 2*(32 + 16)
          = 148 + 68 + 2*(48)
          = 148 + 68 + 96
          = 312 Answer

Regards,
Subhash

 


 
Re: Fibonacci Series- Counting and Recursion
by TG Team - Monday, 26 April 2010, 05:15 PM
 

Subhash smile

Your recursion is correct but f1 = 1, f2 = 2, f3 = 5, f4 = 11 are the first four values. Check this again.

Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Monday, 26 April 2010, 09:05 PM
  Dear sir,
           You are correct. Only now i am having some clear conception.
As you said, f1 = 1,f2 = 2, f3 = 5 & f4 = 11, which are shown in cases 1,2,3 & 4 respectively in the file attached along with this post.

Also,
      fn = fn-1 + fn-2 + 2fn-3 + 2fn-4 ....(1)

      f5 = f4 + f3 + 2*(f2 + f1)
          = 11 + 5 + 2*(2+1)
          = 16 + 2*3 = 16 + 6 = 22
      f6 = f5 + f4 + 2*(f3 +f2)
          = 22 + 11 + 2*(5 + 2)
          = 33 + 2*7
          = 33 + 14
          = 47
      f7 = f6 + f5 + 2*(f4 + f3)
          = 47 + 22 + 2*(11 + 5)
          = 69 + 2*16
          = 69 + 32
          = 101
       f8 = f7 + f6 + 2*(f5 + f4)
           = 101 + 47 + 2*(22 + 11)
           = 214
       f9 = f8 + f7 + 2*(f6 + f5)
           = 214 + 101 + 2*(47 + 22)
           = 453
      f10 = f9 + f8 + 2*(f7 + f6)
           = 453 + 214 + 2*(101 + 47)
           = 963 Answer

Regards,
Subhash
Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Tuesday, 27 April 2010, 09:15 AM
  Dear sir,
           I think my solution for Qn 7 is wrong. The following should be the correct solution for Qn 7.

According to the question, there are 12 persons seated around the table.

Let us assume that n persons seated around the table can shake hands with each other in fn ways.

Now, a single person alone cannot shake hands with himself. Therefore, f1 = 0.
Therefore, the remaining n-1 persons can shake hands in fn-1 ways.

Any two people can shake hands with each other in 2c2 = 1 way.Therefore, the remaining n-2 persons can shake hands with each other in fn-2 ways.

Therefore,
               fn = fn-1 + fn-2 + 1
Taking n = 12, we get,
                f12 = f11 + f10 + 1
                     = 2 + 2f10 +f9
                     .
                     .
                     .
                     .
                     .
                     = 152 Answer

Regards,
Subhash
Re: Fibonacci Series- Counting and Recursion
by TG Team - Wednesday, 28 April 2010, 11:32 AM
 

Subhash smile

There is one extra condition which you have overlooked. No arms cross.

Suppose if 1st and 3rd person are shaking hands, then 2nd cannot shake hands with anybody.

Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Thursday, 20 May 2010, 02:17 AM
  And what if the 1st and the 4th persons shake hands? the 2nd and 3rd persons could then shake hands with each other then? How to approach the solution to this problem? can you give some hints?
Re: Fibonacci Series- Counting and Recursion
by TG Team - Thursday, 20 May 2010, 12:35 PM
 

Welcome Subhashsmile

After almost a month.

See in the question it is said that six pairs of person are shaking hand, that means person 1 cannot shake hands with person 3. So person 1 can shake hands with person 2 or person 4 or person 6 or person 8 or person 10 or person 12 leaving an even number of person on either side in each case.

I think this hint is enough till here.smile

 

Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Thursday, 20 May 2010, 07:37 PM
  Dear sir,
           I had been to my home town and i did not have net connection in my home.So, i could not log in to TG.Also, i was going through the lessons in TG(which i had downloaded earlier).

Now,
       since there would be three persons in two groups(for even numbered and odd numbered places), we will have to find the number of handshakes exchanged in a single group and then square that value.

Let us take any of the two groups. Let fn be the number of ways handshakes could be exchanged by the n people of the group.

A single person cannot shake hands with himself. So, f1 = 0.

Two people can shake hands in 2C2 = 1 way.

Any single person can exchange n-1 handshakes with n -1 remaining people.
So, if we remove any 1 person from the group, n -1 handshakes would be lost.

Let fn-1 be the number of handshakes exchanged by the remaining n-1 people amongst themselves. 

Therefore,
               fn = fn-1 + (n-1)

               f2 = f1 + (2-1)
                   = 0  + 1
                   = 1
                f3 = f2 + 2
                    = 1 + 2
                    = 3
                f4 = f3 + 3
                    = 3 + 3
                    = 6
                f5 = f4 + 4
                    = 6 + 4
                    = 10
                f6 = f5 + 5
                    = 10 + 5
                    = 15

Similarly, 15 handshakes can be exchanged in the other group too. So, total number of ways in which handshakes could be exchanged = 15 * 15
                                                                                   = 225

I think this should be the solution.
        
Re: Fibonacci Series- Counting and Recursion
by TG Team - Friday, 21 May 2010, 12:16 PM
 

Subhash smile

I told you earlier that person 1 cannot shake hands with person 3 or person 5 or person 7 or person 9 or person 11 because then he will be having odd number of persons on his both sides which cannot make a pair to shake hands.

Try to understand that everybody is shaking hand with somebody else provided their arms do not cross.

For example: in a group of four persons only, we will have 2 pairs shaking hands in two ways (i.e. 1-2, 3-4 or 1-4, 2-3). Here 1-3 is not a valid pair as then 2 and 4 can not shake hands.

I hope that question is clear now.smile 

Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Friday, 21 May 2010, 04:26 PM
  Dear sir,
           Let me try again.

Since, person 1 could shake hands with person 2, person 4, person 6, person 8 person 10 or person 12, let us fix a single pair to implement the recursion.

Let fn be the number of handshakes exchanged between n people.

Let us take 1-6 as the reference pair. This pair would add a single handshake. Now the people on either side of this pair would be divided into two groups.

As original number of people is n, one of the groups of people would have n/2 number of people and the other would have n/2-2 number of people.

Also, we can fix the reference pair n/2 times.

Therefore, the recursion would be
fn = (n/2) * {1 + (fn/2)*(fn/2-2)}.........(1)

(We have to multiply the total number of handshakes on each side with each other to get the total number of combinations)
 
Also, a single person cannot shake hands with himself,hence, f1 = f0 = 0...(2)
Two people can shake hands amongst themselves in 2C2 = 1 way.Hence, f2 = 1....(3)
Three people can shake hands, 3C2 = 3 ways.Hence, f3 = 3 .....(4)

Putting n= 12 and using (1),(2) and (3) we get,
 
f12 = 6 * { 1 + (f6)*(f4) }
     = 6 * { 1 +  {3 * (1 + f3 * f1)} * { 2 * ( 1 + f2 * f0 ) } }
     = 6 * { 1 + {3 * (1 + 3 * 0)} * { 2 * ( 1 + 1 * 0)} }
     = 6 * { 1 + { 3 * 1} * { 2 * 1} }
     = 6 * { 1 + 3 * 2 }
     = 6 * { 1 + 6 }
     = 6 * 7
     = 42

I think, answer should be 42 handshakes.

Regards,
Subhash
Re: Fibonacci Series- Counting and Recursion
by TG Team - Friday, 21 May 2010, 05:10 PM
 

Subhashsmile

How can this be true?

"Three people can shake hands, 3C2 = 3 ways.Hence, f3 = 3 .....(4)"

Because There can never be three people on one side of a hand shaking pair. Or we can say that if number of people is odd in that case everybody cannot have a partner to shake hands with. So f(odd) = 0

So if 1-6 is a pair, then there are two groups 2-3-4-5 and 7-8-9-10-11-12.

Recursively let's find out: f(2), f(4), f(6), and so on.
 

Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Friday, 21 May 2010, 07:09 PM
  Dear sir,
           is the recursion formula which i have used in my previous post correct ? Should i approach in the same way while finding the values of f(2),f(4),f(6) etc. ?

Regards,
Subhash
Re: Fibonacci Series- Counting and Recursion
by TG Team - Friday, 21 May 2010, 07:18 PM
 

Subhashsmile

There lies the flaw that f(odd) is zero which you have not accounted for.

Think simply. f(2) = 1.

f(4) = 1-2 + 1-4 = f(2) + f(2) = 2

f(6) = 1-2 + 1-4 + 1-6 = f(4) + f(2)f(2) + f(4) = 5

f(8) = 1-2 + 1-4 + 1-6 + 1-8 = f(6) + f(2)f(4) + f(4)f(2) + f(6) = 14 and so on.smile 

Re: Fibonacci Series- Counting and Recursion
by Subhash Medhi - Friday, 21 May 2010, 10:57 PM
  Dear sir,
            f(10) = 1-2 + 1-4 + 1-6 + 1-8 + 1-10
                    = f(8) + f(2)f(6) + f(4)f(4) + f(6)f(2) + f(8)
                    = 14 + 1*5 + 2*2 + 5*1 + 14
                    = 42
            f(12) = 1-2 + 1-4 + 1-6 + 1-8 + 1-10 + 1-12
                     = f(10) + f(2)f(8) + f(4)f(6) + f(6)f(4) + f(8)f(2) + f(10)
                     = 42 + 1*14 + 2*5 + 5*2 + 14*1 + 42
                     = 42 + 14 + 10 + 10 + 14 + 42
                     = 132
This way, there should be 132 handshakes.

Sir, is there no other way of solving this problem ?

Regards,
Subhash
                     
Re: Fibonacci Series- Counting and Recursion
by TG Team - Saturday, 22 May 2010, 10:26 AM
 

Yessmile

Your answer is correct.

And yes, there is another way of solving this problem.

Basically we need to join the 12 vertices of a 12-gon with 6 diagonals such that no diagonal intersects. This is given by catalan number which is 2n!/n!(n + 1)!

In this case,  n = 6. So our answer is: 12!/6!7! = (12*11*10*9*8)/(6*5*4*3*2*1) = 132. smile

Check for earlier values by yourself and verify. 

 

Re: Fibonacci Series- Counting and Recursion
by Sivaramakrishnan Iyer - Monday, 31 May 2010, 05:04 PM
 

Sir,

Could you please explain the solution for the 7th problem again. I am not able to understand the concept you used there properly. the solution I am refferring to is the one above the catalan number solution.

Siva

 

Re: Fibonacci Series- Counting and Recursion
by TG Team - Monday, 31 May 2010, 06:22 PM
 

Hi Siva smile

If I am not mistaken, you are asking about the handshake problem.

Take a smaller case: If there are only two persons then required number of ways are, say f(2) = 1 only, isn't it? (i.e. 1-2 is making a pair)

Now if we have four persons (say 1, 2, 3, 4 in order), then number of ways are f(4) = 1-2 + 1-4 (i.e. 1 paired with 2 or 1 paired with 4 as 1 can't be paired with 3. Why????)

So, f(4) = f(2) + f(2) = 2.

Going similarly, f(6) = 1-2 + 1-4 + 1-6 = f(4) + f(2)f(2) + f(4) = 5 and so on.smile

If you can find the answer to that Why???? you are done. smile 

Re: Fibonacci Series- Counting and Recursion
by Sivaramakrishnan Iyer - Monday, 31 May 2010, 10:47 PM
  Hello again,

Yeah I got the why .... 1 cant be paired with three coz if it did, then 2 cannot pair with 4, it ll violate the condition.
But what I dont understand is that how is f(6)=5. F(6) = 1-2 +1-4 + 1-6 = f(2) + f(2) + f(2) right??....so it gotta be 3.

Could you please explain that part.

Siva
Re: Fibonacci Series- Counting and Recursion
by Sugam Kuchhal - Wednesday, 2 June 2010, 03:37 AM
 

Hello TGians,

 

First post, so pardon me for mistakes.

I think the solution is wrong here for question 5.

From my understanding the formula is

Fn = (new ways to arrange 1 unit area)*Fn-1 + (new ways to arrange 2 unit area)*Fn-2 + so on till all the possible new ways to arrange are exhausted....

So till now the formaula is ; Fn 

= 1*Fn-1 (due to vertical block)

+ 1*Fn-2 (due to 2 horizontal blocks, which is a new way other than 2 vertical blocks, hence the multiplier is 1)

+ 2*Fn-3 (2 Ls adujsted, and also the can be done upside down, hence 2 new ways, so the multiplier) 

+ 2*Fn-4 (2 Ls with a horizontal stick in middle, and upside down accounts for 2 multiplier).

 

But, I believe many configurations have not yet been tried,

like 2 Ls with 2 horizontal sticks in the middle making a 2*5 area

like 2 Ls with 3 horizontal sticks in the middle making a 2*6 area

4 with 2*7..... so on till (n-3) with 2*n area with all having a 2 multiplier factor due to upside down configuration.

 

Please comment and validate.

Regards

Sugam

 

 

 

Re: Fibonacci Series- Counting and Recursion
by TG Team - Wednesday, 2 June 2010, 12:31 PM
 

Hi Sugamsmile

Accepted and validated.smile

Re: Fibonacci Series- Counting and Recursion
by TG Team - Wednesday, 2 June 2010, 12:36 PM
 

Sivasmile

F(6) = 1-2 + 1-4 + 1-6

1-2 means if 1 is paired with 2, then other 4 persons (3, 4, 5, 6) can be paired in F(4) ways.

1-4 means 1 is paired with 4, the on one side of this pair are two persons (2, 3) and on other side also there are two persons (5, 6) which can be paired in F(2) ways each. So total F(2)F(2) ways of pairing for 1-4.

1-6 means 1 is paired with 6 and other 4 persons (2, 3, 4, 5) can be paired in F(4) ways.

Is it clear now? smile

Re: Fibonacci Series- Counting and Recursion
by Sivaramakrishnan Iyer - Wednesday, 2 June 2010, 02:37 PM
 

Thank you sir

I got it now. Must say this, good explanation. smile

Re: Fibonacci Series- Counting and Recursion
by sandeep kumar - Monday, 12 July 2010, 11:41 PM
  Dear Sir,
very useful article ,thank you. Is answer for fair toss question is 73 ,x+y=9+64?
Re: Fibonacci Series- Counting and Recursion
by mohil mittal - Tuesday, 13 July 2010, 09:13 PM
  sir,

how to create a recursion for Q-6?

what i could infer is, it follows a pattern which seems to be a finite series of e^(-x)

If we find out the quantity of liquid in urn 1 its

1-1/2+1/2*1/3-1/2*1/3*1/4...............close to 2009 terms

nw hw to add up this series ??

Re: Fibonacci Series- Counting and Recursion
by TG Team - Wednesday, 14 July 2010, 07:40 PM
 

Hi Sandeepsmile

Thanks for comment.

Yes. Your answer is perfectly fine.smile

Re: Fibonacci Series- Counting and Recursion
by TG Team - Wednesday, 14 July 2010, 07:53 PM
 

Hi Mohit smile

Just try to see the pattern of the quantities in the two urns. Refer to a post above by Subhash Medhi.

Re: Fibonacci Series- Counting and Recursion
by mohil mittal - Wednesday, 14 July 2010, 11:07 PM
  sir,

i perfectly agree with the way subhash has solved the problem.
I had another query regarding the way i tried to figure out the problem


how to find sum to n terms for the series


1+x/1!+x^2/2!+x^3/3!.............................x^n/n!??

which seems to be a finite e^x series.
Re: Fibonacci Series- Counting and Recursion
by mohil mittal - Wednesday, 14 July 2010, 11:16 PM
  BTW sir its mohil smile
Re: Fibonacci Series- Counting and Recursion
by Durgadas Haldar - Thursday, 22 July 2010, 08:42 PM
 

I think Postman wala explanation is not correct...as we can hv many more cases...Believe that this question should be done by p&C instead of Fibonacci

Re: Fibonacci Series- Counting and Recursion
by TG Team - Friday, 23 July 2010, 01:10 PM
 

Hi Durgadas smile

I'd love to believe you. Please solve it.

Re: Fibonacci Series- Counting and Recursion
by sharad mishra - Sunday, 8 August 2010, 03:58 AM
  thanx kamal sir and sorry for the mistake. shy
Re: Fibonacci Series- Counting and Recursion
by SHAUNAK A - Sunday, 27 February 2011, 08:51 AM
  For Q5, will the recursion be of form:

A(n) = A(n-1) + A(n-2) + 2*A(n-3) + 2*A(n-4) + 2*A(n-5)

Is this right or are there other arrangements as well?

Re: Fibonacci Series- Counting and Recursion
by TG Team - Monday, 28 February 2011, 06:12 PM
  Hi Shaunak smile
Actually it is:
A(n) = A(n - 1) + A(n - 2) + 2[A(n - 3) + A(n - 4) + A(n - 5) + ..... + A(1)] + 2, for all n > 2
i.e.
A(1) = 1
A(2) = 2
A(3) = 2 + 1 + 2 = 5
A(4) = 5 + 2 + 2[1] + 2 = 11
A(5) = 11 + 5 + 2[2 + 1] + 2 = 24
A(6) = 24 + 11 + 2[5 + 2 + 1] + 2 = 53
A(7) = 53 + 24 + 2[11 + 5 + 2 + 1] + 2 = 117
A(8) = 117 + 53 + 2[24 + 11 + 5 + 2 + 1] + 2 = 258 and so on... smile

With this I am getting another pattern i.e. A(n) = 2A(n - 1) + A(n - 3)

Kamal Lohia
 
Re: Fibonacci Series- Counting and Recursion
by SHAUNAK A - Monday, 28 February 2011, 09:22 PM
 
Sir, can u elaborate it using diagrams...

I got till 2*A(n-5), but then i got the diagram for A(n-6)

As in the attached pic, 2*A(n-6) / 2*A(n-7)...will continue as 2*1 tiles can be laid horizontally on 1 another after 1st 1 Lshaped one and the last one L shaped 1.

The interim tiles can be 1/2/3/4....
Re: Fibonacci Series- Counting and Recursion
by saanthwana T - Saturday, 14 May 2011, 12:45 AM
  getting confused abt the staircase of 10 steps problem

Am I wrong in saying 1 single step + n steps can be covered in 2xan ways?
where first way is : first 1 step and then n steps
ans second way is : first n steps and then 1 step

I am facing the same confjusion for the TG tower with pink and yellow floors problem
Please clarify
Re: Fibonacci Series- Counting and Recursion
by mohil mittal - Wednesday, 5 October 2011, 11:12 AM
  somebdy please post the solution steps for Mr. BLck, Mr red, mr orange derangement question!!
Re: Fibonacci Series- Counting and Recursion
by Arpit Jain - Sunday, 16 October 2011, 08:30 PM
  Nice article!

I have gone through several(almost all) articles here,but one thing I found lacking in most of the articles is that official solutions are not posted for the exercises which are given at the end of the article. sad
If not complete solutions with explanations,please post only official answers only after a certain time frame. This will help us to know whether we solved the questions correctly or not.
Finding solutions in comments sometimes become a lot difficult.

Kamal Sir,
Please post solutions of above questions which you gave as exercise.
Re: Fibonacci Series- Counting and Recursion
by Prerna Golani - Tuesday, 29 May 2012, 12:41 PM
  How 1-2 means if 1 is paired with 2, then other 4 persons (3, 4, 5, 6) can be paired in F(4) ways.Can u explain?
Re: Fibonacci Series- Counting and Recursion
by Varun Katiyar - Wednesday, 6 June 2012, 06:45 PM
 

Why n+1 is taken as 10.

In earlier post also it was mentioned that for fn+1 was ways to arrange n digits. Thus for 10 digits (as in the question) why dint we took n=10 and calculated f11 as the answer ?

 

Re: Fibonacci Series- Counting and Recursion
by Pratibha B - Thursday, 23 August 2012, 12:57 PM
  Hi Kamal,

The answer to question on tossing of coin is 1535.
Probability is 511/1024 as per my calculation.

Please let me know if it is correct.


Re: Fibonacci Series- Counting and Recursion
by TG Team - Saturday, 25 August 2012, 06:44 PM
 

Hi Pratibha smile

Please post the question also with your answer, so that it may be easy for everyone to respond quickly. smile

Re: Fibonacci Series- Counting and Recursion
by gaurav midha - Tuesday, 2 October 2012, 06:32 PM
  Hi Kamal Sir,

Can you please explain derangement more with giving examples.

It is confusing.I didn't get anything from above.

Thanks.


Regards,
GM
Re: Fibonacci Series- Counting and Recursion
by rimmi rimmi - Wednesday, 3 October 2012, 02:16 AM
  thank u so much for this wonderful lesson smile

sir, what will be the product of 1^1*2^2*3^3*…..*49^49?
smile
Re: Fibonacci Series- Counting and Recursion
by asheet raina - Wednesday, 3 October 2012, 02:59 PM
  hi sir,lovely article.....  i have been reading  your articles of late. it won't be wrong to say that i have fallen in love  with what you do
Re: Fibonacci Series- Counting and Recursion
by asheet raina - Wednesday, 3 October 2012, 03:05 PM
 

hi rimmi,

separate the powers of 2, 3, 5, 7, 11, 13... till all prime no.s are covered.the highest prime no. will be 47.... u try once... if u can't solve , i shall do it for you then.37 raised to power 37  n 43 raised to power 43...  will b  quite easier, bcoz you will not have any other power of these prime no.s...every prime no. after 25  will come only once.....29 raised to power 29  n so on as two no.s abv... tc... 

Re: Fibonacci Series- Counting and Recursion
by asheet raina - Wednesday, 3 October 2012, 03:06 PM
 

hi rimmi,

separate the powers of 2, 3, 5, 7, 11, 13... till all prime no.s are covered.the highest prime no. will be 47.... u try once... if u can't solve , i shall do it for you then.37 raised to power 37  n 43 raised to power 43...  will b  quite easier, bcoz you will not have any other power of these prime no.s...every prime no. after 25  will come only once.....29 raised to power 29  n so on as two no.s abv... tc... 

Re: Fibonacci Series- Counting and Recursion
by Abhinay Swarup - Monday, 7 September 2015, 07:40 PM
  Dear Sir,

For 1st question I got 194.
going backwards i got a7= 5a1 + 8a2 so a1 =8 & a2=10 gives a8 194.
However, i have doubt whether a1 can take 0 and a2 15 as they are positive integer.
kindly explain.
In that case a8 will be different.

Regards,
Abhinay
Re: Fibonacci Series- Counting and Recursion
by Abhinay Swarup - Monday, 7 September 2015, 08:42 PM
  Very good article. Another way to handle problems..