using System;

using System.Collections.Generic;

using System.Linq;

using System.Web;

​

public class Program

{

    public static void Main()

    {

        for(int i=0; i<20; i++)

            Console.WriteLine(Fibonacci(i));

            Console.WriteLine(IsFibonacci(21));

    }

​

​

    public static int Fibonacci(int n)

    {

        if(n <=1)

            return n;

        else return Fibonacci(n-1)+Fibonacci(n-2);

    }

    public static bool IsFibonacci(uint n)

    {

        return IsPerfectSquare(5*n*n + 4) ||

           IsPerfectSquare(5*n*n - 4);

    }

    static bool IsPerfectSquare(uint x)

    {

        return (Math.Sqrt(x) % 1 == 0);

    }

}