0/1 tiles problem. I need the mathematical soln for this.

[sheldonshiva]

Problem 1: 0/1 Tiles
To help Lavanya learn all about binary numbers and binary sequences, her father has bought her a collection of square tiles, each of which has either a 0 or a 1 written on it. Her brother Nikhil has played a rather nasty prank. He has glued together pairs of tiles with 0 written on them. Lavanya now has square tiles with 1 on them and rectangular tiles with two 0's on them, made up of two square tiles with 0 stuck together). Thus, she can no longer make all possible binary sequences using these tiles.
To amuse herself, Lavanya has decided to pick a number N and try and construct as many binary sequences of length N as possible using her collection of tiles. For example if N = 1, she can only make the sequence 1. For N=2, she can make 11 and 00. For N=4, there are 5 possiblities: 0011, 0000, 1001, 1100 and 1111.
Lavanya would like you to write a program to compute the number of arrangements possible with N tiles so that she can verify that she has generated all of them. Since she cannot count beyond 15746, it is sufficient to report this number modulo 15746.
Input format
A single line with a single integer N.
Output format
A single integer indicating the number of binary sequences of length N, modulo 15746, that Lavanya can make using her tiles.
Test data
You may assume that N ≤ 1000000.
Example
Here is a sample input and output corresponding to the example discussed above.
Sample input
4
Sample output
5

CPU Timelimit: 3 seconds
Memory limit: 64M
Grading style:ioi


this is the problem. i need some mathematical logical answer behind it.

[cspctec]

This is my take on it.

N = 1 -> Output = 1
N = 2 -> Output = 2
N = 3 -> Output = 3
N = 4 -> Output = 5
N = 5 -> Output = 8
N = 6 -> Output = 13
N = 7 -> Output = 21

I wrote the binary sequences down on some paper and figured out the first 5 possible values with the 0's glued together, then I tried to recognize a pattern, and to me it looks like the Fibonacci sequence. It is not very difficult to code the Fibonacci sequence:

#include <iostream>

using namespace std;

int compute(int n)
{
    if (n <= 3)
    {
        return n;
    }

    else
    {
        return compute(n - 1) + compute(n - 2);
    }
}

int main()
{
    int n;

    cout << "Input integer N: ";
    cin >> n;
    cin.ignore();

    cout << "\nNumber of combinations: " << compute(n);

    cin.get();
    return 0;
}

I don't know about the rest of it (the mod 15746, not sure where that comes in). Maybe you can figure out the rest of it. I hope this is at least a little help. You probably know more about it than me since you were most likely in class.