#include <stdio.h>
//a{n} = 2a{n-1} + a{n-2}, a{1}=2, a{2}=3(再帰なし版)
int rec(int n){
	if(n==1) return 2;
	else if(n==2) return 3;
	return 2*rec(n-1) + rec(n-2);
}
int main(void) {
    int n = 4;
    int a, b = 3, c = 2; 
    for(int i = 3; i <= n; i++){
        a = 2*b + c; //a{n} = 2a{n-1} + a{n-2}
        c = b; // a{n-2} = a{n-1}
        b = a; // a{n-1} = a{n}
    }
    printf("数列a%dの値は%d\n", n, a);
 
    printf("再帰で求めた数列a%dの値は%d",n,rec(n));
	return 0;
}
 
 

I2luY2x1ZGUgPHN0ZGlvLmg+Ci8vYXtufSA9IDJhe24tMX0gKyBhe24tMn0sIGF7MX09MiwgYXsyfT0zKOWGjeW4sOOBquOBl+eJiCkKaW50IHJlYyhpbnQgbil7CglpZihuPT0xKSByZXR1cm4gMjsKCWVsc2UgaWYobj09MikgcmV0dXJuIDM7CglyZXR1cm4gMipyZWMobi0xKSArIHJlYyhuLTIpOwp9CmludCBtYWluKHZvaWQpIHsKICAgIGludCBuID0gNDsKICAgIGludCBhLCBiID0gMywgYyA9IDI7IAogICAgZm9yKGludCBpID0gMzsgaSA8PSBuOyBpKyspewogICAgICAgIGEgPSAyKmIgKyBjOyAvL2F7bn0gPSAyYXtuLTF9ICsgYXtuLTJ9CiAgICAgICAgYyA9IGI7IC8vIGF7bi0yfSA9IGF7bi0xfQogICAgICAgIGIgPSBhOyAvLyBhe24tMX0gPSBhe259CiAgICB9CiAgICBwcmludGYoIuaVsOWIl2ElZOOBruWApOOBryVkXG4iLCBuLCBhKTsKICAgIAogICAgcHJpbnRmKCLlho3luLDjgafmsYLjgoHjgZ/mlbDliJdhJWTjga7lgKTjga8lZCIsbixyZWMobikpOwoJcmV0dXJuIDA7Cn0KCg==