Число Фибоначчи с полным квадрат

Question

задание

Показать, что 2ⁿ⁺¹ – 7f²_n-1, есть полный квадрат. А как это реализовать я не понимаю, подскажите что нужно подставить, вот код

public class Two {
public static void main(String[] args) {
    int f1 = -1;
    int f2 = 1;
    int z;
    Scanner scanner = new Scanner(System.in);
    int fn = scanner.nextInt();
    for (int i = 2;  i < fn; i++ ){
       int f = -f2 - 2 * f1;
       f1 = f2;
       f2 = f;
       System.out.print("\n" + f );
     }

   }
}

Answer 1

Нужно определить рекурсивную функцию в соответствии с заданной формулой:

static int fn(int n) {
    if (n == 1) return 1;
    if (n == 2) return -1;
    return -fn(n - 1) - 2 * fn(n - 2);
}

и проверить выражение 2ⁿ⁺¹ - 7 * f_n-1² в цикле:

int p2 = 2;
int fnprev = 0;
for (int n = 1; n < 30; n++) {
    int fni = fn(n);
    System.out.printf("fn(%2d)=%5d\t", n, fni);
    p2 *= 2;
    if (n > 1) {
        int x = 7*fnprev*fnprev;
        System.out.println("2^(" + (n+1) +") - 7*(" + fnprev + ")^2 = "
                + p2 + " - " + x + " = " + (p2-x) + " = " 
                + (int)Math.sqrt(p2-x) + "^2"
        );
    }
    else {
        System.out.println();
    }
    fnprev = fni;
}

Вывод:

fn( 1)=    1    
fn( 2)=   -1    2^(3) - 7*(1)^2 = 8 - 7 = 1 = 1^2
fn( 3)=   -1    2^(4) - 7*(-1)^2 = 16 - 7 = 9 = 3^2
fn( 4)=    3    2^(5) - 7*(-1)^2 = 32 - 7 = 25 = 5^2
fn( 5)=   -1    2^(6) - 7*(3)^2 = 64 - 63 = 1 = 1^2
fn( 6)=   -5    2^(7) - 7*(-1)^2 = 128 - 7 = 121 = 11^2
fn( 7)=    7    2^(8) - 7*(-5)^2 = 256 - 175 = 81 = 9^2
fn( 8)=    3    2^(9) - 7*(7)^2 = 512 - 343 = 169 = 13^2
fn( 9)=  -17    2^(10) - 7*(3)^2 = 1024 - 63 = 961 = 31^2
fn(10)=   11    2^(11) - 7*(-17)^2 = 2048 - 2023 = 25 = 5^2
fn(11)=   23    2^(12) - 7*(11)^2 = 4096 - 847 = 3249 = 57^2
fn(12)=  -45    2^(13) - 7*(23)^2 = 8192 - 3703 = 4489 = 67^2
fn(13)=   -1    2^(14) - 7*(-45)^2 = 16384 - 14175 = 2209 = 47^2
fn(14)=   91    2^(15) - 7*(-1)^2 = 32768 - 7 = 32761 = 181^2
fn(15)=  -89    2^(16) - 7*(91)^2 = 65536 - 57967 = 7569 = 87^2
fn(16)=  -93    2^(17) - 7*(-89)^2 = 131072 - 55447 = 75625 = 275^2
fn(17)=  271    2^(18) - 7*(-93)^2 = 262144 - 60543 = 201601 = 449^2
fn(18)=  -85    2^(19) - 7*(271)^2 = 524288 - 514087 = 10201 = 101^2
fn(19)= -457    2^(20) - 7*(-85)^2 = 1048576 - 50575 = 998001 = 999^2
fn(20)=  627    2^(21) - 7*(-457)^2 = 2097152 - 1461943 = 635209 = 797^2
fn(21)=  287    2^(22) - 7*(627)^2 = 4194304 - 2751903 = 1442401 = 1201^2
fn(22)=-1541    2^(23) - 7*(287)^2 = 8388608 - 576583 = 7812025 = 2795^2
fn(23)=  967    2^(24) - 7*(-1541)^2 = 16777216 - 16622767 = 154449 = 393^2
fn(24)= 2115    2^(25) - 7*(967)^2 = 33554432 - 6545623 = 27008809 = 5197^2
fn(25)=-4049    2^(26) - 7*(2115)^2 = 67108864 - 31312575 = 35796289 = 5983^2
fn(26)= -181    2^(27) - 7*(-4049)^2 = 134217728 - 114760807 = 19456921 = 4411^2
fn(27)= 8279    2^(28) - 7*(-181)^2 = 268435456 - 229327 = 268206129 = 16377^2
fn(28)=-7917    2^(29) - 7*(8279)^2 = 536870912 - 479792887 = 57078025 = 7555^2
fn(29)=-8641    2^(30) - 7*(-7917)^2 = 1073741824 - 438752223 = 634989601 = 25199^2

Но доказывать данное утверждение надо по индукции.

БЛОГ НА HUSL

Число Фибоначчи с полным квадрат

Ответы (1 шт):