Solution to task 2

1 files changed, 36 insertions, 0 deletions

diff --git a/challenge-112/jo-37/perl/ch-2.pl b/challenge-112/jo-37/perl/ch-2.pl
new file mode 100755
index 0000000000..9eb1ffb432
--- /dev/null
+++ b/challenge-112/jo-37/perl/ch-2.pl
@@ -0,0 +1,36 @@
+#!/usr/bin/perl -s
+
+use v5.16;
+use warnings;
+use Math::Prime::Util 'lucasu';
+
+die <<EOS unless @ARGV;
+usage: $0 N
+
+N
+    Count the different ways to climb a stair of N steps taking either
+    one ore two steps at a time.
+
+EOS
+
+# Are Abigail and Abigail the same person?  See perlsecret.
+<<m=~m>>
+Let S(n) be the number of different ways to climb a stair of n steps
+taking either one ore two steps at a time.
+
+Let n > 2.  The last move is either one step with S(n-1) ways to reach
+the second last step or two steps with S(n-2) ways to reach the step
+before it.
+
+Thus S(n) = S(n-1) + S(n-2).  Furthermore, the trivial cases S(1) = 1
+and S(2) = 2 lead to S(n) = Fₙ₊₁, the (n+1)th Fibonacci number.
+
+The Fibonacci sequence Fₙ is the particular Lucas sequence Uₙ(1, -1) as
+provided by Math::Prime::Util.
+
+See e.g. http://oeis.org/wiki/Lucas_sequences.
+
+m
+;
+
+say lucasu 1, -1, 1 + shift;