From 028a12d2d851f05a95b879392c8dae6eef7655f9 Mon Sep 17 00:00:00 2001
From: Jörg Sommrey <28217714+jo-37@users.noreply.github.com>
Date: Mon, 10 May 2021 12:17:25 +0200
Subject: Solution to task 2

---
 challenge-112/jo-37/perl/ch-2.pl | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
 create mode 100755 challenge-112/jo-37/perl/ch-2.pl

(limited to 'challenge-112/jo-37')

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;
-- 
cgit