perl-scripts/Math/fibonacci_polynomials_closed_form.pl

#!/usr/bin/perl

# Closed-form expression for Fibonacci polynomials:
#    Sum_{k=0..n} (fibonacci(k) * x^k)

# Formulas generated by Wolfram|Alpha.

# See also:
#   https://projecteuler.net/problem=435

use 5.020;
use strict;
use warnings;

use experimental qw(signatures);
use Math::AnyNum qw(:overload);

sub F1 ($n, $x) {
    (2**(-$n-1)*$x*(2*sqrt(5)*(1+sqrt(5))**$n*$x**($n+1)+(5+sqrt(5))*(1+sqrt(5))**$n*$x**$n-2*sqrt(5)*$x*($x-sqrt(5)*$x)**$n-sqrt(5)*($x-sqrt(5)*$x)**$n+5*($x-sqrt(5)*$x)**$n-5*2**($n+1)))/(5*($x**2+$x-1));
}

sub F2 ($n, $x) {
    -(2**(2-$n)*(1+sqrt(5))**(-1-$n)*$x*((2*(1+sqrt(5)))**$n*(5+3*sqrt(5))-((-4)**$n*(1+sqrt(5))+2*(1+sqrt(5))**(2*$n)*(2+sqrt(5)))*$x**$n+(3+sqrt(5))*((-4)**$n-(1+sqrt(5))**(2*$n))*$x**(1+$n)))/(sqrt(5)*(1+sqrt(5)+2*$x)*(-2+$x+sqrt(5)*$x));
}

say F1(7, 11);      #=> 268357683
say F2(7, 11);      #=> =//=