# Faces of Fibonacci

You know about the Fibonacci numbers and you know how Matrix Exponentiation allows you to find the nth Fibonacci number in just O(logn) time.

Matrix Exponentiation is a useful tool in solving not just the questions related to Fibonacci numbers but other recurrence equations too.

The equation:
f(n) = a*f(n-1) + b*f(n-2)
can be disguised and thrown at you in numerous ways.

I’m going to use a familiar problem to show you how.

SAMPLE PROBLEM:
We have the following types of rectangles with us:
1. size 1 X 1
2. size 2 X 1
In how many ways can we form a rectangle of size N X 1 by putting the mentioned types of rectangles side by side.

To form rectangle of size 1 X 1 there is only one way. That is to use one rectangle of size 1 X 1.
To form rectangle of size 2 X 1 there are two ways: the first is to use a 2 X 1 rectangle directly and the second way is to put two 1 X 1 rectangles side by side.
To form rectangle of size 3 X 1 there are 3 ways. For 4 X 1, there are 5 ways..

Lets analyze this problem in a recursive manner:

Let f(n) be the number of ways to form an N X 1 rectangle.
An N X 1 rectangle can be formed either by adding a 1 X 1 rectangle to the end of an (N-1) X 1 rectangle
OR
by adding a 2 X 1 rectangle to the end of an (N-2) X 1 rectangle
Therefore, the number of ways to form N X 1 rectangle = (number of ways to form (N-1) X 1 rectangle) + (number of ways to form (N-2) X 1 rectangle)
f(n) = f(n-1) + f(n-2) ; with f(0)=1 and f(1)=1
Its the Fibonacci series!!

( f(0)=1 because there is 1 way to form a 0 X 1 rectangle: do not use any rectangle )

Let’s look at a variation.

SAMPLE PROBLEM:
We have the following types of rectangles with us:
1. size 1 X 1 of two different types: red- and blue-colored
2. size 2 X 1

In how many ways can we form a rectangle of size N X 1 by putting the mentioned types of rectangles side by side.

An N X 1 rectangle can be formed either by adding a 2 X 1 rectangle to the end of an (N-2) X 1 rectangle
OR
by adding a blue 1 X 1 rectangle to the end of an (N-1) X 1 rectangle
OR
by adding a red 1 X 1 rectangle to the end of an (N-1) X 1 rectangle
So, there are two ways to obtain N X 1 rectangle from an (N-1) X 1 rectangle, and only one way to get it from an (N-2) X 1 rectangle.
The equation becomes f(n) = 2*f(n-1) + 1*f(n-2) ; with f(0)=1 and f(1)=2

In general, if we have 1 X 1 rectangles of X different colors and 2 X 1 rectangles of Y different colors, we can make an N X 1 rectangle in f(n) ways, f(n) = X*f(n-1) + Y*f(n-2); with f(0)=1 and f(1)=X

We can add another twist…

SAMPLE PROBLEM:
We have the following types of rectangles with us:
1. size 1 X 1 of X different colors
2. size 2 X 1 of Y different colors
3. size 3 X 1 of Z different colors

In how many ways can we form a rectangle of size N X 1 by putting the mentioned types of rectangles side by side.

In this case the number of ways to construct an N X 1 rectangle = f(n) = X * f(n-1) + Y * f(n-2) + Z * f(n-3) ; with f(0)=1, f(1)=X,f(2)=X+Y

All of the above variations can be solved using Matrix Exponentiation. We just need to find the exponentiation matrix carefully.

Apart from ‘number of ways to form rectangles’, in a programming problem you could be asked to compute the number of ways to climb stairs or many other variations.
This page contains many interesting questions.

The ability to decompose a problem into its sub-problems and to compute its solution from the solution of its sub-problems is very useful in solving many Dynamic programming, Recurrance equation and Graph related problems.

If you have any doubt, feel free to leave a comment here.

Advertisements
{"ft_lang_label":"__label__en","ft_lang_prob":0.8838139,"math_prob":0.9942542,"size":3583,"snap":"2019-13-2019-22","text_gpt3_token_len":1041,"char_repetition_ratio":0.19195306,"word_repetition_ratio":0.2768595,"special_character_ratio":0.29137594,"punctuation_ratio":0.06921241,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9997111,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-05-19T22:23:51Z\",\"WARC-Record-ID\":\"<urn:uuid:5134cdcf-90c2-4887-a1b2-068835bd7266>\",\"Content-Length\":\"55381\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:54041cb4-70fe-40fc-ad4e-f95c7ac8dade>\",\"WARC-Concurrent-To\":\"<urn:uuid:47b9963a-6376-4c37-a540-611e230215ff>\",\"WARC-IP-Address\":\"192.0.78.12\",\"WARC-Target-URI\":\"https://codeaccepted.wordpress.com/2014/10/02/faces-of-fibonacci/\",\"WARC-Payload-Digest\":\"sha1:F7WGOLJVXUO7DQPXLENJI2IBWRYGMVXT\",\"WARC-Block-Digest\":\"sha1:FTY2HULRAL22QMJI6OOIAVVHB2UQLXU3\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-22/CC-MAIN-2019-22_segments_1558232255182.37_warc_CC-MAIN-20190519221616-20190520003616-00042.warc.gz\"}"}