this is the actual question
Often poetic meters of some fixed beat length (per line) have some rhythmic pattern composed of light and heavy syllables from the source language (for example, English or Sanskrit). It is common to treat the light syllable to measure as being 1 beat in length, while a heavy syllable to measure as 2 beats. In such a framework, given a fixed beat length of n, write a program that can compute the total number of patterns involving light and/or heavy syllables? As an example, a line with a fixed beat length of 5 can be composed of a pattern that is light-light-heavy-light (1+1+2+1=5), or heavy-light-heavy (2+1+2=5), or any one of the other six possible patterns.
Now I know this is a programming question but I realise that it is actually a fibonacci recursive relation where $f(N) = f(N-1) + f(N-2)$
My only problem is that I can't seem to prove it
Hint: A permissible sequence of length $n$ either begins with a light beat followed by a permissible sequence of length $n - 1$ or a heavy beat followed by a permissible sequence of length $n - 2$.