OSP Informathic 2008 :

Upik clever mathematics, but he only can write numbers 1 and 2. Therefore, when Upik want to write a number of more than 2, they write some of number 1 and number 2 a few. For example to write down the number 3, right Upik have 3 ways: 12, 21, or 111 (1 + 2 = 3, 2 + 1 = 3; 1 + 1 + 1 = 3). To write down the number 2, in fact Upik have 2 ways: 2 and 11 (2 = 2, 1 + 1 = 2), but there is only 1 way to write down the number 1. How many ways to write the number 8?

Discussion:

In fact, only the array fibonacci course we can already do. Is it only that? Let's see.
To write the number 1, requires a ways (1)
To write the number 2, requires 2 ways (11, 2)
To write a number 3, requires 3 ways (111, 12, 21)
To write the number 4, requires 5 ways (1111, 112, 211, 121, 22)
From way above, we have found the pattern of progression fibonacci.

1	2	3	4	5	6	7	8	9	10
1	2	3	5	8	13	21	34	55	89

From the table above we can see that:
To write the number 5, requires 8 ways.
To write the number 6, requires 13 ways.
To write the number 7, requires 21 ways. And,
To write the number 8, requires 34 ways

So to write the number 8, there are 34 ways