フィボナッチ数列で遊んだ

# フィボナッチ数列を定義する
## 漸化式での定義
フィボナッチ数列は数学者レオナルド・フィボナッチに因んで名付けられた数で、漸化式を使って次のように表現することができます。

```math
\begin{align}
F_0&=0\\
F_1&=1\\
F_{n+2}&=F_{n+1}+F_{n} (n \geq 0)
\end{align}
```

これを計算して１項目から順に並べると

```math
1,1,2,3,5 \cdots
```

となります。C++での実装例は以下の通り。

```c++
#include <stdio.h>
#define N 15
int main() {
    int i;
    int* F;
    F = new int[N+1];
    F[0] = 0;
    F[1] = 1;

    printf("1 -> %d \r\n", F[1]);

    for (i = 2; i < N+1; i++) {
        F[i] = F[i - 2] + F[i - 1];
        printf("%d -> %d \r\n", i, F[i]);
    }

    delete[] F;
}
```

C++として振る舞うコードはメモリの動的確保を行う部分

``` C++
F = new int[N+1];

//省略

delete[] F;
```

であるので、malloc等に置き換えればC言語として実行することができます。mallocで実行するにはヘッダーに

```c
#include <cstdlib> // for malloc
```

を追加し

```c
F = (int *)malloc(sizeof(int)*(N+1));

//省略

free(F);
```

とすると動くと思います。

## フィボナッチ数列の一般解を使った定義

漸化式的な計算はメモリが必要だったりと面倒です。そこで一般解を使って各項を計算することを考えます。フィボナッチ数列の一般解はすでに得られていて

```math
\begin{align}
F(n)&=\frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}} \\
\phi&=\frac{1+\sqrt{5}}{2}
\end{align}
```

となります。一般解を用いてフィボナッチ数列を計算するC++での実装例は以下の通り。

```c++
#include <stdio.h>
#include <math.h>
#define n 15
int main(){
    int i;
    double phi = (1 + sqrt(5)) / 2;
    for (i = 1; i <= n; i++) {
        printf("%d -> %f\r\n",i, (pow(phi,i) - pow(-phi,-i)) / sqrt(5));
    }
}
```

ここで累乗は

```c
#include <math.h>
```

を追加し

```c
int y;
y=pow(a,x);
```

とすれば

```math
y=a^x
```

を計算できます。

# フィボナッチ数列の関係式
フィボナッチ数列にはいくつかの関係が知られています。これをプログラムで計算して確かめてみます。

## フィボナッチ数列の特别な和公式
```math
\begin{align}
\sum_{i=1}^\infty  \frac{F_i}{10^{i+1}} = \frac{1}{89}
\end{align}
```

```c
#include <stdio.h>
#include <math.h>
#define N 30
const double phi = (1 + sqrt(5)) / 2;
double Fibonacci(int);
int main() {
    int i, n;
    double psi = 0;
    for (i = 1; i <= N; i++) {
        n = i + 1;
        psi = psi + Fibonacci(i) / pow(10, n);
        printf("%f -> %f \r\n",1/89.0,  psi);
    }
}

double Fibonacci(int i) {
    return (pow(phi, i) - pow(-phi, -i)) / sqrt(5);
}
```

## フィボナッチ数列の逆数和

```math
\begin{align}
\psi=\sum_{i=1}^\infty  \frac{1}{F_i} = 3.3498 \cdots
\end{align}
```

```c
#include <stdio.h>
#include <math.h>
#define n 30
const double phi = (1 + sqrt(5)) / 2;
double Fibonacci(int);
int main() {
    int i;
    double psi = 0;
    for (i = 1; i <= n; i++) {
        psi = psi + 1 / Fibonacci(i);
        printf("%d -> %f\r\n",i, psi);
    }
}

double Fibonacci(int i) {
    return (pow(phi, i) - pow(-phi, -i)) / sqrt(5);
}
```

## フィボナッチ数列の比の極限

```math
\begin{align}
\lim_{n \to \infty } \frac{F_{n+1}}{F_n}= \phi = \frac{1 + \sqrt{5}}{2}
\end{align}
```

```c
#include <stdio.h>
#include <math.h>
#define n 30
const double phi = (1 + sqrt(5)) / 2;
double Fibonacci(int);
int main() {
    int i;
    for (i = 2; i <= n; i++) {
        printf("%f -> %f\r\n", phi, Fibonacci(i) / Fibonacci(i - 1));
    }
}

double Fibonacci(int i) {
    return (pow(phi, i) - pow(-phi, -i)) / sqrt(5);
}
```


## 連続する１０個のフィボナッチ数列の和と７番目の数との関係

```math
\begin{align}
\sum_{i=1}^{10}  F_{n+i} = 11 \times F_{n+7}
\end{align}
```

```c
#include <stdio.h>
#include <math.h>
#define N 9
const double phi = (1 + sqrt(5)) / 2;
double Fibonacci(int);
int main() {
    int i;
    double psi = 0;
    for (i = 1; i <= 10; i++) {
        psi = psi + Fibonacci(N + i);
    }
    printf("%f -> %f \r\n", 11*Fibonacci(N+7), psi);
}

double Fibonacci(int i) {
    return (pow(phi, i) - pow(-phi, -i)) / sqrt(5);
}
```

# 参考
・[Wikipedia フィボナッチ数列](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0)

・[しろねこらぼ（ブログ）](https://sironekolab.com/?s=%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0%E5%88%97)