fibonacci identity

fib5.pl

sub choose {
  my ($n, $k) = @_;
  return 1 if $k == 0;
  return 0 if $n == 0;
  return choose($n-1, $k-1) * $n / $k;
}

sub pow5 {
  my ($k) = @_;
  my $p = 1;
  $p *= 5 while $k--;
  return $p;
}

for my $N (0..20) {
  my $t = 0;
  for my $k (0 .. int(($N-1)/2)) {
    $t += choose($N, 2*$k+1) * pow5($k);
  }

  $t >>= ($N-1); # divide by 2^(n-1)                                            

  printf "%2d %4d\n", $N, $t;
}